记录编号	253255	评测结果	WWWWWWWWWW
题目名称	罪犯问题C	最终得分	0
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.652 s
提交时间	2016-04-21 20:51:50	内存使用	23.95 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
//#include"debug.h"
using namespace std;

const int maxl=400010;
struct edge{
	int t,oppo,g;bool x;
}w[2*maxl];
//w[i]表示由w[i].f能推出w[i].t，且二人的性质相同=w[i].b 
int n,m,k,head[maxl],tail[maxl],next[maxl],i,j,cnt;
int hash[maxl],s,t;
bool visit[maxl];
//hash[i]=1表示i是罪犯，hash[i]=-1表示i不是罪犯，hash[i]=0表示不清楚i是否是罪犯 

void dfs(int x){
	if (visit[x]) return;
	visit[x]=true;
	for (int i=head[x];i!=0;i=next[i]){
		hash[w[i].t]=hash[x]*(w[i].x?1:-1);
		dfs(w[i].t);
	}
}
void add(int f,int t,int g){
	cnt++;w[cnt].t=t;w[cnt].g=g;w[cnt].oppo=cnt+1;
	if (head[f]==0) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	cnt++;w[cnt].t=f;w[cnt].oppo=cnt-1;
	if (head[t]==0) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}

struct stack{
	int x,i,df;
}z[maxl];
int top,l[maxl],ans,d[maxl],r;
void change(){
	int df=z[top].df,i;
	ans+=z[top].df;
	for (i=top-1;i>0;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].oppo].g+=df;
		z[i].df-=df;
		if (z[i].df==0) top=i;
	}
}
void bfs(){
	int i,j;
	l[s]=1;d[r=1]=s;
	for (i=1;i<=n;i++) l[i]=-1;
	for (i=1;i<=r;i++)
	for (j=head[d[i]];j!=0;j=next[j])
	if (l[w[j].t]==-1&&w[j].g>0){
		l[w[j].t]=l[d[i]]+1;d[++r]=w[j].t;
	}
}
bool dinic(){
	bfs();
	if (l[t]==-1) return false;
	top=1;z[1].x=s;z[1].df=99999999;z[1].i=head[s];
	while (top>0){
		if (z[top].x==t){
			change();top--;z[top].i=next[z[top].i];continue;
		}
		if (z[top].i==0){
			l[z[top].x]=-1;top--;continue;
		}
		if (w[z[top].i].g>0&&l[w[z[top].i].t]==l[z[top].x]+1){
			z[top+1].x=w[z[top].i].t;
			z[top+1].i=head[z[top+1].x];
			z[top+1].df=min(z[top].df,w[z[top].i].g);
			top++;
			continue;
		}
		z[top].i=next[z[top].i];
	}
	return true;
}

int main()
{
	freopen("criminalc.in","r",stdin);
	freopen("criminalc.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	cnt=n*2;
	for (i=1;i<=m;i++){
		scanf("%d",&j);hash[j]=1;
		add(0,1,99999999);
	}
	
	for (i=1;i<=n;i++){
		scanf("%d",&w[i].t);
		w[i].x=(w[i].t<0);
		w[i].t=abs(w[i].t);
		w[i].g=1;
		w[i].oppo=i+n;
		if (head[i]==0) head[i]=tail[i]=i;
			else tail[i]=next[tail[i]]=i;
		w[i+n].t=i;
		w[i+n].x=w[i].x;
		w[i+n].g=1;
		w[i+n].oppo=i;
		if (head[w[i].t]==0) head[w[i].t]=tail[w[i].t]=i+n;
			else tail[w[i].t]=next[tail[w[i].t]]=i+n;
	}
	for (i=1;i<=n;i++)
	if (hash[i]!=0&&!visit[i]) dfs(i);
	
	//print(hash,1,n,' ');
	if (hash[k]!=1){
		printf("0\n");return 0;
	}
	
	s=0;t=k;
	while (dinic());
	printf("%d\n",ans);
	return 0;
}