[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查
这个是一道题啊……不过都是挺经典的问题……
建图是这样的：支持0的从向此点连一条容量为1的边，支持1的就向
连一条长度为1的边，朋友之间连一条长度为1的边。跑一遍最小割即可。
这个的解释？最优情况下任何人违背自己的意见都是因为怕和朋友冲突，和朋友冲突则是因为没有违背自己的意见（废话）。所以拆了最小割就解决掉了所有冲突问题。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | /************************************************************** Problem: 2768 User: danihao123 Language: C++ Result: Accepted Time:60 ms Memory:7668 kb****************************************************************/ #include <cstdio>#include <cstring>#include <queue>#include <vector>#include <algorithm>using namespace std;const int maxn=305;namespace Dinic{ struct Edge{ int u,v,cap,flow; }; vector<Edge> edges; vector<int> G[maxn]; int s,t; int m; inline void AddEdge(int u,int v,int cap){ edges.push_back((Edge){u,v,cap,0}); edges.push_back((Edge){v,u,0,0}); m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } bool vis[maxn]; int cur[maxn],d[maxn]; bool bfs(){ register int i,u; queue<int> Q; memset(vis,0,sizeof(vis)); Q.push(s); d[s]=0; vis[s]=true; while(!Q.empty()){ u=Q.front(); Q.pop(); for(i=0;i<G[u].size();i++){ Edge& e=edges[G[u][i]]; if(!vis[e.v] && e.cap>e.flow){ d[e.v]=d[u]+1; Q.push(e.v); vis[e.v]=true; } } } return vis[t]; } int dfs(int x,int a){ if(x==t || a==0) return a; int f,flow=0; for(int& i=cur[x];i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){ flow+=f; e.flow+=f; edges[G[x][i]^1].flow-=f; a-=f; if(a==0) break; } } return flow; } int MinCut(int S,int T){ register int ans=0; s=S; t=T; while(bfs()){ memset(cur,0,sizeof(cur)); ans+=dfs(s,0x7fffffff); } return ans; }};int main(){ int n,m; int u,v; register int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&u); if(!u){ Dinic::AddEdge(0,i,1); }else{ Dinic::AddEdge(i,n+1,1); } } for(i=1;i<=m;i++){ scanf("%d%d",&u,&v); Dinic::AddEdge(u,v,1); Dinic::AddEdge(v,u,1); } printf("%d\n",Dinic::MinCut(0,n+1)); return 0;} |
