题意：有N个人，每个人有一个初始想法(0/1)和ki个朋友，安排每个人的最终想法，使得|违心的人数+不同意见的朋友的对数|最小
题解：
S向每个0连流量为1的边，表示违心；同理每个1向T连流量为1的边。如果两人是朋友，连一条流量为1的边，表示可以对立。
然后网络流/最小割走起。
#include#include #include #include #include #include #include using namespace std;const int MAXN=300+2;struct HASH{ int u; HASH *next; HASH(){} HASH(int _u,HASH *_next):u(_u),next(_next){}}*tab[MAXN],*cur[MAXN],mem[2*MAXN*MAXN];struct EDGE{ int u,c; EDGE(){} EDGE(int _u,int _c):u(_u),c(_c){}}e[2*MAXN*MAXN];int N,M,cnt,d[MAXN];queue q;void Insert(int u,int v,int c){ tab[u]=&(mem[cnt]=HASH(cnt,tab[u])),e[cnt++]=EDGE(v,c); tab[v]=&(mem[cnt]=HASH(cnt,tab[v])),e[cnt++]=EDGE(u,0);}bool BFS(int S,int T){ memset(d,-1,sizeof(d)); d[S]=0,q.push(S); int x; while(!q.empty()){ x=q.front(),q.pop(); for(HASH *p=tab[x];p;p=p->next) if(e[p->u].c && d[e[p->u].u]<0) d[e[p->u].u]=d[x]+1,q.push(e[p->u].u); } return d[T]>0;}int DFS(int x,int f,int t){ if(x==t) return f; int flow,used=0; for(HASH *p=cur[x];p;p=p->next) if(e[p->u].c && d[e[p->u].u]==d[x]+1){ flow=DFS(e[p->u].u,min(f-used,e[p->u].c),t); e[p->u].c-=flow,e[p->u^1].c+=flow,used+=flow; if(e[p->u].c) cur[x]=p; if(used==f) return f; } if(!used) d[x]=-1; return used;}int Dinic(int S,int T){ int ret=0; while(BFS(S,T)){ memcpy(cur,tab,sizeof(tab)); ret+=DFS(S,INT_MAX,T); } return ret;}int main(){ scanf("%d %d",&N,&M); for(int i=1,t;i<=N;i++){ scanf("%d",&t); if(t) Insert(i,N+1,1); else Insert(0,i,1); } for(int i=1,u,v;i<=M;i++){ scanf("%d %d",&u,&v); Insert(u,v,1),Insert(v,u,1); } printf("%d\n",Dinic(0,N+1)); return 0;}