描述

幼兒園里有n個(gè)小朋友打算通過(guò)投票來(lái)決定睡不睡午覺(jué)。對(duì)他們來(lái)說(shuō)，這個(gè)問(wèn)題并不是很重要，于是他們決定發(fā)揚(yáng)謙讓精神。雖然每個(gè)人都有自己的主見(jiàn)，但是為了照顧一下自己朋友的想法，他們也可以投和自己本來(lái)意愿相反的票。我們定義一次投票的沖突數(shù)為好朋友之間發(fā)生沖突的總數(shù)加上和所有和自己本來(lái)意愿發(fā)生沖突的人數(shù)。我們的問(wèn)題就是，每位小朋友應(yīng)該怎樣投票，才能使沖突數(shù)最小？

分析

• 一個(gè)沖突對(duì)應(yīng)一個(gè)割, 沖突數(shù)最少就是求最小割 --- 不懂
• 感性的分析一下, 如果 s->x (x->t) 的邊在最小割中, 表示x改變意愿. 如果 x->y 的邊在最小割中, 表示 x 和 y 之間到最后還存在著沖突.

代碼 #include #include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 300 + 10; struct Edge { int from, to, cap, flow; }; struct Dinic { int n, m, s, t; vectoredges; vectorG[maxn]; bool vis[maxn]; int d[maxn], cur[maxn]; void init(int n, int s, int t) { this->n = n; this->s = s; this->t = t; } void AddEdge(int from, int to, int cap, int _cap=0) { edges.push_back((Edge){from, to, cap, 0}); edges.push_back((Edge){to, from, _cap, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queueQ; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow() { int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } }g; int main() { int n, m, s, t; scanf("%d %d", &n, &m); s = 0; t = n+1; g.init(n+2, s, t); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); if(x) g.AddEdge(s, i, 1); else g.AddEdge(i, t, 1); } for(int i = 0; i < m; i++) { int from, to; scanf("%d %d", &from, &to); g.AddEdge(from, to, 1, 1); } printf("%d\n", g.Maxflow()); return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ-1934-Vote善意的投票-SHOI2007的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。