一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。
2≤n≤300
网上的大爷们都说是裸的最小割,然而我想了好久最后还是看了题解。。。
一开始的想法是把若有人放在一侧,把所有关系看做点放在一侧,然后建图最小割,结果捣鼓了半天都没搞出啥大新闻。
把该图看成二分图,若x支持切尔西,则s到x连边,否则x到t连边。
对于一对朋友关系(x,y),从x到y连一条边,从y到x连一条边,流量均为1。
不难验证最小割即是答案。
双倍经验:bzoj 1934
#include#include #include #include #include #include using namespace std; const int N=305; const int inf=1000000000; int n,m,dis[N],cur[N],last[N],cnt,a[N],s,t; struct edge{int to,next,c;}e[N*N*2]; queue que; int read() { int x=0,f=1;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; } void addedge(int u,int v,int c) { e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt; } bool bfs() { for (int i=s;i<=t;i++) dis[i]=0; while (!que.empty()) que.pop(); dis[s]=1;que.push(s); while (!que.empty()) { int u=que.front();que.pop(); for (int i=last[u];i;i=e[i].next) if (e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==t) return 1; que.push(e[i].to); } } return 0; } int dfs(int x,int maxf) { if (x==t||!maxf) return maxf; int ret=0; for (int i=last[x];i;i=e[i].next) if (e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(e[i].c,maxf-ret)); e[i].c-=f; e[i^1].c+=f; ret+=f; if (maxf==ret) break; } return ret; } int dinic() { int ans=0; while (bfs()) { for (int i=s;i<=t;i++) cur[i]=last[i]; ans+=dfs(s,inf); } return ans; } int main() { n=read();m=read();s=0;t=n+1;cnt=1; for (int i=1;i<=n;i++) { a[i]=read(); if (a[i]) addedge(i,t,1); else addedge(s,i,1); } for (int i=1;i<=m;i++) { int x=read(),y=read(); addedge(x,y,1);addedge(y,x,1); } printf("%d",dinic()); return 0; }