最小割，考虑最小割就是要将整张图分为两块，本题中就分别表示赞同和不赞同，那么首先一开始赞同的点向S连边，不赞同的点向T连边，如果这些点分到了另一边就要割掉这条边，朋友关系同理，连双向边同样表示分到两边要割掉这条边，跑最小割=最大流即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 305 4 struct ji{ 5 int nex,to,len; 6 }edge[N*N]; 7 queue<int>q; 8 int E,n,m,x,y,head[N],work[N],d[N]; 9 void add(int x,int y,int z){ 10 edge[E].nex=head[x]; 11 edge[E].to=y; 12 edge[E].len=z; 13 head[x]=E++; 14 if (E&1)add(y,x,0); 15 } 16 bool bfs(){ 17 memset(d,-1,sizeof(d)); 18 q.push(0); 19 d[0]=0; 20 while (!q.empty()){ 21 int k=q.front(); 22 q.pop(); 23 for(int i=head[k];i!=-1;i=edge[i].nex) 24 if ((edge[i].len)&&(d[edge[i].to]<0)){ 25 d[edge[i].to]=d[k]+1; 26 q.push(edge[i].to); 27 } 28 } 29 return d[n+1]>=0; 30 } 31 int dfs(int k,int s){ 32 if (k>n)return s; 33 int p; 34 for(int &i=work[k];i!=-1;i=edge[i].nex) 35 if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){ 36 p=dfs(edge[i].to,min(s,edge[i].len)); 37 if (p){ 38 edge[i].len-=p; 39 edge[i^1].len+=p; 40 return p; 41 } 42 } 43 return 0; 44 } 45 int main(){ 46 scanf("%d%d",&n,&m); 47 memset(head,-1,sizeof(head)); 48 for(int i=1;i<=n;i++){ 49 scanf("%d",&x); 50 if (x)add(0,i,1); 51 else add(i,n+1,1); 52 } 53 for(int i=1;i<=m;i++){ 54 scanf("%d%d",&x,&y); 55 add(x,y,1); 56 edge[E-1].len=1; 57 } 58 int ans=0; 59 while (bfs()){ 60 memcpy(work,head,sizeof(head)); 61 while (x=dfs(0,0x3f3f3f3f))ans+=x; 62 } 63 printf("%d",ans); 64 }