A Plug for UNIX (Network Flow-Maximum Flow-dinic Algorithms)

A Plug for UNIX (Network Flow-Maximum Flow-dinic Algorithms)

judge: POJ 1087
Time Limit: 1000MS
Memory Limit: 65536K
source: East Central North America 1999

Description

You are in charge of setting up the press room for the inaugural meeting of the United Nations Internet eXecutive (UNIX), which has an international mandate to make the free
......
POJ 1087

Input

POJ 1087

Sample Input

4
A
B
C
D
5
laptop B
phone C
pager B
clock B
comb X
3
B X
X A
X D

Sample Output

1

meaning of the title

The title is not very easy to understand. It's probably like this: there is a room with n sockets, each socket is different, and each socket has only one. At this time, there are m kinds of electrical appliances, telling you what type of socket each electrical appliances corresponds to, and also gives you some converters, A-B is plug A can be plugged into socket B. Ask you how many electrical outlets you have at least. Namely: Plug Number - Maximum Matching

Establish super source point and super sink point, connect plug to source point, connect socket to sink point, and then according to the socket connection point corresponding to each plug:
Add the converter:
Note that although the converter is infinite, the socket is limited, so the converter is equivalent to only one for each.
And then we began to connect happily (__)y

Code

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <map>
#include <string>
#define _for(i, a) for(int i = 0; i < (a); i++)
#define _rep(i, a, b) for(int i = (a); i <= (b); i++)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
using namespace std;

struct poi {
	int u, v, cap, next;//w 0 drinks	1 vegetable
}edges[maxn];

int head[maxn], cnt;
int n, m, k;
int dis[maxn];
int S, T;
int cur[maxn];
map<string, int> mp;
vector<int> num[maxn];

void init() {
	memset(head, -1, sizeof(head));
	memset(edges, 0, sizeof(edges));
	cnt = 0;
	memset(num, 0, sizeof(num));
}

void adde(int u, int v, int w) {
	edges[cnt].u = u, edges[cnt].v = v, edges[cnt].cap = w;
	edges[cnt].next = head[u], head[u] = cnt++;
	edges[cnt].u = v, edges[cnt].v = u, edges[cnt].cap = 0;
	edges[cnt].next = head[v], head[v] = cnt++;
}

//bfs hierarchy
bool bfs() {
	memset(dis, 0, sizeof(dis));
	dis[S] = 1;
	queue<int> Q;
	Q.push(S);
	int flow = 0;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i = head[u]; ~i; i = edges[i].next) {
			int v = edges[i].v, cap = edges[i].cap;
			if (cap > 0 && !dis[v]) {
				dis[v] = dis[u] + 1;
				Q.push(v);
			}
		}
	}
	return dis[T] != 0;
}

//dfs seeks augmentation path
int dfs(int u, int mw) {
	if (u == T || mw == 0) return mw;
	int flow = 0;
	for (int &i = cur[u]; ~i; i = edges[i].next) {
		int v = edges[i].v, cap = edges[i].cap;
		if (cap > 0 && dis[v] == dis[u] + 1) {
			int cw = dfs(v, min(mw, cap));
			flow += cw;
			edges[i].cap -= cw;
			edges[i ^ 1].cap += cw;
			mw -= cw;
			if (mw == 0) break;
		}
	}
	return flow;
}

//Main process
int dinic() {
	int res = 0;
	while (bfs()) {
		memcpy(cur, head, sizeof(head));
		res += dfs(S, inf);
	}
	return res;
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	while (cin >> n) {
		init();
		string c;
		_rep(i, 1, n) {
			cin >> c;
			mp[c] = i;
		}
		cin >> m;
		_rep(i, n + 1, n + m) {
			cin >> c;
			cin >> c;
			if (!mp.count(c)) mp[c] = mp.size() + 1;
			num[i].push_back(mp[c]);
		}

		S = n + m + 1;
		T = S + 1;

		_rep(i, 1, n) adde(i, T, 1);

		cin >> k;
		_rep(i, 1, k) {
			string u, v;
			cin >> u >> v;
			adde(mp[u], mp[v], inf);
		}
		_rep(i, n + 1, n + m) {
			adde(S, i, 1);
			_for(j, num[i].size()) {
				adde(i, num[i][j], 1);
			}
		}
		cout << m - dinic() << "\n";
	}
	return 0;
}

Tags: socket Unix network iOS

Posted on Wed, 09 Oct 2019 23:25:59 -0700 by Entanio