[JLOI2010]冠军调查同[SHOI2007]Vote 善意的投票
看到这种题目就知道要跑网络流啦。只要把赞成的连原点流量为1,反对连汇点流量为1,其他每个朋友互相连一条流量为一的边,然后跑一遍最短路就好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 302 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch=getchar(); while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f; } int n,m,ans; struct Edge{ int x,y,c,next,other; }E[Maxn*Maxn+1];int len,first[Maxn+3]; void ins(int x,int y,int c){ len++; E[len].x=x;E[len].y=y;E[len].c=c; E[len].next=first[x];first[x]=len;E[len].other=len+1; len++; E[len].x=y;E[len].y=x;E[len].c=0; E[len].next=first[y];first[y]=len;E[len].other=len-1; } int st,ed,h[Maxn+3]; bool v[Maxn+3]; std::queue<int>q; bool bt(){ q.push(st); mes(h,0);h[st]=1; mes(v,false);v[st]=true; while(q.empty()==false){ int x=q.front(); for(int k=first[x];k>0;k=E[k].next){ int y=E[k].y; if(h[y]==0&&E[k].c>0){ h[y]=h[x]+1; if(v[y]==false){ v[y]=true; q.push(y); } } } v[x]=false; q.pop(); } if(h[ed]>0)return true; else return false; } int findflow(int x,int f){ if(x==ed)return f; int s=0,tmp; for(int k=first[x];k>0;k=E[k].next){ int y=E[k].y; if(E[k].c>0&&h[y]==h[x]+1&&s<f){ tmp=findflow(y,std::min(E[k].c,f-s)); s+=tmp; E[k].c-=tmp;E[E[k].other].c+=tmp; } } if(s==0)h[x]=0; return s; } int main(){ qread(n);qread(m); st=n+1;ed=st+1; len=0;mes(first,0); for(int i=1;i<=n;i++){ int qread(x); if(x==1)ins(st,i,1); else ins(i,ed,1); } for(int i=1;i<=m;i++){ int qread(x),qread(y); ins(x,y,1);ins(y,x,1); } ans=0; while(bt()==true)ans+=findflow(st,INF); printf("%d\n",ans); } |