题意:每个人可能选0或者1,而且每个人有一些朋友,当他和朋友意见不同的时候,他是可能违背自己的内心而去迎合朋友的,现在问你最好的发言情况下,说谎的人加上意见不同的朋友总数最少,最少是多少

题解:最小割模型

        对于每个人,想选0的,build(s,v,1);想选1的,build(v,t,1);

        因为朋友关系是双向的,build(u,v,1),build(v,u,1);

　　 因为对于每个人来说 要么割掉这个人 要么割掉这个人和他的朋友的边

        最小割就刚刚好是答案

        因为你割掉的朋友的边就是意见不同的朋友数量 你割掉的连向s或者t的边就是说谎的人

1 #include
     
       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 Rec10     {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