來自FallDream的博客，未經允許，請勿轉載，謝謝。

---

幼兒園里有n個小朋友打算通過投票來決定睡不睡午覺。對他們來說，這個問題并不是很重要，于是他們決定發揚謙讓精神。雖然每個人都有自己的主見，但是為了照顧一下自己朋友的想法，他們也可以投和自己本來意愿相反的票。我們定義一次投票的沖突數為好朋友之間發生沖突的總數加上和所有和自己本來意愿發生沖突的人數。 我們的問題就是，每位小朋友應該怎樣投票，才能使沖突數最小？

n<=300

每個小朋友如果想睡覺那么從S向他連邊，如果想修仙從它向T連邊，然后朋友之間互相連邊。

#include<iostream> #include<cstring> #include<cstdio> #define S 0 #define T 301 #define INF 2000000000 using namespace std; inline 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; }int n,m,q[T+5],top=0,head[T+5],c[T+5],d[T+5],cnt=1,ans=0; struct edge{int to,next,w;}e[T*T*10+5];void ins(int f,int t,int w) {e[++cnt]=(edge){t,head[f],w};head[f]=cnt;e[++cnt]=(edge){f,head[t],0};head[t]=cnt; }int dfs(int x,int f) {if(x==T) return f;int used=0;for(int&i=c[x];i;i=e[i].next)if(e[i].w&&d[e[i].to]==d[x]+1){int w=dfs(e[i].to,min(f-used,e[i].w));used+=w;e[i].w-=w;e[i^1].w+=w;if(f==used) return f; }return d[x]=-1,used; }bool bfs() {memset(d,0,sizeof(d));int i,j;for(d[q[top=i=1]=S]=1;i<=top;++i)for(int j=c[q[i]]=head[q[i]];j;j=e[j].next)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T]; }int main() {n=read();m=read();for(int i=1;i<=n;i++) read()?ins(S,i,1):ins(i,T,1);for(int i=1;i<=m;i++){int x=read(),y=read();ins(x,y,1);ins(y,x,1); }while(bfs()) ans+=dfs(S,INF);cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/bzoj1934.html

總結

以上是生活随笔為你收集整理的[bzoj1934][Shoi2007]Vote 善意的投票的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。