Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:Dinic算法一次AIn Reply To:Dinic算法一次A Posted by:1917 at 2014-04-18 21:08:35 > #include<iostream> > #include<cstring> > #include<string> > #include<queue> > #include<map> > using namespace std; > const int MAX = 100000; > const int INF = 0xfffffff; > > struct Edge{ > int v, f, nxt; > }; > int n, m, k; > int src, sink; > int nume = 1; > int num = 1; > map<string,int> rec_dev; > int g[MAX]; > Edge e[MAX]; > int dist[MAX], vis[MAX]; > string plux, device; > void addEdge(int u, int v, int c) > { > e[++nume].v = v; > e[nume].f = c; > e[nume].nxt = g[u]; > g[u] = nume; > } > void BFS() > { > memset(vis, 0, sizeof(vis)); > queue<int> que; > que.push(src); > dist[src] = 0; > vis[src] = 1; > while(!que.empty()) { > int u = que.front(); > que.pop(); > for(int i = g[u]; i; i = e[i].nxt) > if(e[i].f && !vis[e[i].v]) { > que.push(e[i].v); > dist[e[i].v] = dist[u] + 1; > vis[e[i].v] = 1; > } > } > } > int DFS(int u, int delta) > { > if(u == sink) > return delta; > int ret = 0; > for(int i = g[u]; delta && i; i = e[i].nxt) > if(dist[e[i].v] == dist[u]+1) { //e[i].f && > int dd = DFS(e[i].v, e[i].f<delta?e[i].f:delta); > e[i].f -= dd; > e[i^1].f += dd; > delta -= dd; > ret += dd; > } > return ret; > } > int Dinic() > { > int ret = 0; > while(true) { > memset(dist, 0, sizeof(dist)); > BFS(); > while(!vis[sink]) > return ret; > ret += DFS(src, INF); > } > } > int main() > { > memset(g, 0, sizeof(g)); > src = 1; sink = MAX-1; > cin>>n; > for(int i = 1; i <= n; i++) { > cin>>plux; > rec_dev[plux] = ++num; > addEdge(num, sink, 1); > addEdge(sink, num, 0); > } > cin>>m; > for(int i = 1; i <= m; i++) { > cin>>device>>plux; > rec_dev[device] = ++num; > if(!rec_dev[plux]) > rec_dev[plux] = ++num; > addEdge(src, rec_dev[device], 1); > addEdge(rec_dev[device], src, 0); > addEdge(rec_dev[device], rec_dev[plux], 1); > addEdge(rec_dev[plux], rec_dev[device], 0); > } > cin>>k; > for(int i = 1; i <= k; i++) { > cin>>device>>plux; > if(!rec_dev[device]) > rec_dev[device] = ++num; > if(!rec_dev[plux]) > rec_dev[plux] = ++num; > addEdge(rec_dev[device], rec_dev[plux], INF); > addEdge(rec_dev[plux], rec_dev[device], 0); > } > cout<<m-Dinic()<<endl; > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator