Gym - 101845F 最大流

The UN finals are here!, the coaches/ex-coaches team is creating a new exciting contest to select which teams will compete in the Colombian finals. Ivan said: the rules are clear, the only limitation to enroll teams in the Colombian finals is to pick a maximum of k teams per career. A team can be labeled with career X if there is no career Y such that more team members are enrolled in career Y than in career X. Finally, each team consists of three students (as usual).

Someone in the UN campus (UN finals are pretty popular) said, hey you guys should pick the teams careers in such a way that it maximizes the number of enrolled teams. Diego said: ah that is too easy. You will prove Diego right (or wrong). Given the description of the teams, output the maximum number of teams that can be enrolled in the Colombian finals.

Input

The first line is n (1 ≤ n ≤ 100) - the number of teams that registered to participate in the UN finals.

Next n lines contains each the
information from each team, that is, there will be three strings per
team (one per team member) separated by a single space. Each string
consists of distinct upper case letters which represent the careers that
a team member is studying (UN students love to study multiple careers).

The last line contains an integer k (1 ≤ k ≤ n) - the maximum allowed number of teams per career.

Output

Print a single integer - the maximum number of teams that can be enrolled.

Example

Input

5
A ABC B
C C C
B B B
A A A
C AC CB
2

Output

Note

In the first example first and fourth team can represent career A, second and fifth team can represent career C and third can represent team B.

吐槽一点：数据真水，我模拟都过了。。

应该是网络流的裸题；

至于匹配问题的话，匈牙利也可以；

不过网络流建边也比较容易；

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<bitset>

#include<ctime>

#include<deque>

#include<stack>

#include<functional>

#include<sstream>

//#include<cctype>

//#pragma GCC optimize(2)

using namespace std;

#define maxn 200005

#define inf 0x7fffffff

//#define INF 1e18

#define rdint(x) scanf("%d",&x)

#define rdllt(x) scanf("%lld",&x)

#define rdult(x) scanf("%lu",&x)

#define rdlf(x) scanf("%lf",&x)

#define rdstr(x) scanf("%s",x)

typedef long long  ll;

typedef unsigned long long ull;

typedef unsigned int U;

#define ms(x) memset((x),0,sizeof(x))

const long long int mod = 1e9 + 7;

#define Mod 1000000000

#define sq(x) (x)*(x)

#define eps 1e-4

typedef pair<int, int> pii;

#define pi acos(-1.0)

//const int N = 1005;

#define REP(i,n) for(int i=0;i<(n);i++)

typedef pair<int, int> pii;

inline ll rd() {

	ll x = 0;

	char c = getchar();

	bool f = false;

	while (!isdigit(c)) {

		if (c == '-') f = true;

		c = getchar();

	}

	while (isdigit(c)) {

		x = (x << 1) + (x << 3) + (c ^ 48);

		c = getchar();

	}

	return f ? -x : x;

}

ll gcd(ll a, ll b) {

	return b == 0 ? a : gcd(b, a%b);

}

int sqr(int x) { return x * x; }

/*ll ans;

ll exgcd(ll a, ll b, ll &x, ll &y) {

	if (!b) {

		x = 1; y = 0; return a;

	}

	ans = exgcd(b, a%b, x, y);

	ll t = x; x = y; y = t - a / b * y;

	return ans;

}

*/

int n;

int k;

string s[104][3];

map<char, int>mp;

int fg[103][30];

int vis[2000];

int str[1003];

int car[103];

int st, ed;

struct node {

	int u, v, nxt, w;

}edge[maxn << 1];

int head[maxn], cnt;

void addedge(int u, int v, int w) {

	edge[cnt].u = u; edge[cnt].v = v; edge[cnt].nxt = head[u];

	edge[cnt].w = w; head[u] = cnt++;

}

int rk[maxn];

int bfs() {

	queue<int>q;

	ms(rk);

	rk[st] = 1;

	q.push(st);

	while (!q.empty()) {

		int tmp = q.front(); q.pop();

		for (int i = head[tmp]; i != -1; i = edge[i].nxt) {

			int to = edge[i].v;

			if (rk[to] || edge[i].w <= 0)continue;

			rk[to] = rk[tmp] + 1; q.push(to);

		}

	}

	return rk[ed];

}

int dfs(int u, int flow) {

	if (u == ed)return flow;

	int add = 0;

	for (int i = head[u]; i != -1 && add < flow; i = edge[i].nxt) {

		int v = edge[i].v;

		if (rk[v] != rk[u] + 1 || !edge[i].w)continue;

		int tmpadd = dfs(v, min(edge[i].w, flow - add));

		if (!tmpadd) { rk[v] = -1; continue; }

		edge[i].w -= tmpadd; edge[i ^ 1].w += tmpadd;

		add += tmpadd;

	}

	return add;

}

int ans;

void dinic() {

	while (bfs())ans += dfs(st, inf);

}

int main() {

	//   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin >> n; memset(head, -1, sizeof(head));

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= 3; j++)cin >> s[i][j];

	}

	cin >> k;

	for (int i = 1; i <= n; i++) {

		mp.clear();

		for (int j = 1; j <= 3; j++) {

			for (int y = 0; y < s[i][j].length(); y++) {

				mp[s[i][j][y]]++;

			}

		}

		int maxx = -1;

		for (char ch = 'A'; ch <= 'Z'; ch++) {

			maxx = max(maxx, mp[ch]);

		}

		for (char ch = 'A'; ch <= 'Z'; ch++) {

			if (mp[ch] == maxx) {

				fg[i][ch - 'A' + 1] = 1;

			}

		}

	}

	st = 0; ed = 1000;

	for (int i = 1; i <= n; i++)addedge(st, i, 1), addedge(i, st, 0);

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= 26; j++) {

			if (fg[i][j]) {

				addedge(i, j + n + 1, 1); addedge(j + 1 + n, i, 0);

			}

		}

	}

	for (int i = 1; i <= 26; i++)addedge(i + n + 1, ed, k), addedge(ed, i + 1 + n, 0);

	dinic();

	cout << ans << endl;

	return 0;

}

巴特西

Gym - 101845F 最大流

最新文章

热门文章