题意:每个人可能选0或者1,而且每个人有一些朋友,当他和朋友意见不同的时候,他是可能违背自己的内心而去迎合朋友的,现在问你最好的发言情况下,说谎的人加上意见不同的朋友总数最少,最少是多少
题解:最小割模型
对于每个人,想选0的,build(s,v,1);想选1的,build(v,t,1);
因为朋友关系是双向的,build(u,v,1),build(v,u,1);
因为对于每个人来说 要么割掉这个人 要么割掉这个人和他的朋友的边
最小割就刚刚好是答案
因为你割掉的朋友的边就是意见不同的朋友数量 你割掉的连向s或者t的边就是说谎的人
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 350 4 #define M 100000 5 const int inf=0x7fffffff/3; 6 namespace Dinic 7 { 8 int head[N],head2[N],p=1; 9 struct Rec 10 { 11 int go,nex,c; 12 }eg[M*2]; 13 void build(int a,int b,int c) 14 { 15 eg[++p]=(Rec){b,head[a],-c}; 16 head[a]=p; 17 eg[++p]=(Rec){a,head[b],0}; 18 head[b]=p; 19 } 20 int dis[N],Q[N],s[N],S,T,stop,ans; 21 bool bfs() 22 { 23 memset(dis,0,sizeof(dis)); 24 dis[T]=1; 25 Q[1]=T; 26 for (int p1=1,p2=1;p1<=p2;p1++) 27 { 28 for (int i=head[Q[p1]];i;i=eg[i].nex) 29 if (eg[i^1].c<0&&!dis[eg[i].go]) 30 { 31 dis[eg[i].go]=dis[Q[p1]]+1; 32 Q[++p2]=eg[i].go; 33 } 34 } 35 if (!dis[S]) return false; 36 memcpy(head2,head,sizeof(head)); 37 return true; 38 } 39 bool dinic(int p,int top) 40 { 41 if (p==T) 42 { 43 int x=inf; 44 for (int i=1;i<=top-1;i++) if (-eg[s[i]].c<x) x=-eg[s[i]].c,stop=i; 45 for (int i=1;i<=top-1;i++) eg[s[i]].c+=x,eg[s[i]^1].c-=x; 46 ans+=x; 47 return true; 48 } 49 for (int &i=head2[p];i;i=eg[i].nex) 50 { 51 if (eg[i].c<0&&dis[eg[i].go]==dis[p]-1) 52 { 53 s[top]=i; 54 if (dinic(eg[i].go,top+1)&&top!=stop) return true; 55 } 56 } 57 return false; 58 } 59 int ask() 60 { 61 ans=0; 62 while (bfs()) dinic(S,1); 63 return ans; 64 } 65 void init(int _S,int _T){ 66 S=_S,T=_T; 67 } 68 } 69 using namespace Dinic; 70 void clear() 71 { 72 p=1; 73 memset(head,0,sizeof(head)); 74 } 75 int n,m,ss,tt,x,y; 76 int main() 77 { 78 scanf("%d%d",&n,&m); 79 ss=0;tt=n+1; 80 init(ss,tt); 81 for (int i=1;i<=n;i++) 82 { 83 scanf("%d",&x); 84 if (x) build(ss,i,1);else build(i,tt,1); 85 } 86 for (int i=1;i<=m;i++) 87 { 88 scanf("%d%d",&x,&y); 89 build(x,y,1); 90 build(y,x,1); 91 } 92 printf("%d ",ask()); 93 return 0; 94 }