Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:Dinic算法一次A

Posted by fnoi12bzzhan at 2014-12-27 19:20:00 on Problem 1087
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator