呃呃呃呃呃
把每个课给了 INF 个容量.... 我是沙雕把....emm.... 这题就是做着玩... 呃呃呃别当真....
- #include <iostream>
- #include <cstdio>
- #include <sstream>
- #include <cstring>
- #include <map>
- #include <cctype>
- #include <set>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <bitset>
- #define rap(i, a, n) for(int i=a; i<=n; i++)
- #define rep(i, a, n) for(int i=a; i<n; i++)
- #define lap(i, a, n) for(int i=n; i>=a; i--)
- #define lep(i, a, n) for(int i=n; i>a; i--)
- #define rd(a) scanf("%d", &a)
- #define rlld(a) scanf("%lld", &a)
- #define rc(a) scanf("%c", &a)
- #define rs(a) scanf("%s", a)
- #define rb(a) scanf("%lf", &a)
- #define rf(a) scanf("%f", &a)
- #define pd(a) printf("%d\n", a)
- #define plld(a) printf("%lld\n", a)
- #define pc(a) printf("%c\n", a)
- #define ps(a) printf("%s\n", a)
- #define MOD 2018
- #define LL long long
- #define ULL unsigned long long
- #define Pair pair<int, int>
- #define mem(a, b) memset(a, b, sizeof(a))
- #define _ ios_base::sync_with_stdio(0),cin.tie(0)
- //freopen("1.txt", "r", stdin);
- using namespace std;
- const int maxn = 1e5 + 10, INF = 0x7fffffff;
- int head[maxn], cur[maxn], d[maxn], nex[maxn <<1];
- int n, m, s, t;
- int cnt;
- struct node
- {
- int u, v, c;
- }Node[maxn << 1];
- void add_(int u, int v, int c)
- {
- Node[cnt].u = u;
- Node[cnt].v = v;
- Node[cnt].c = c;
- nex[cnt] = head[u];
- head[u] = cnt++;
- }
- void add(int u, int v, int c)
- {
- add_(u, v, c);
- add_(v, u, 0);
- }
- bool bfs()
- {
- queue<int> Q;
- mem(d, 0);
- Q.push(s);
- d[s] = 1;
- while(!Q.empty())
- {
- int u = Q.front(); Q.pop();
- for(int i = head[u]; i != -1; i = nex[i])
- {
- int v = Node[i].v;
- if(!d[v] && Node[i].c> 0)
- {
- d[v] = d[u] + 1;
- Q.push(v);
- if(v == t) return 1;
- }
- }
- }
- return d[t] != 0;
- }
- int dfs(int u, int cap)
- {
- int ret = 0;
- if(u == t || cap == 0) return cap;
- for(int &i = cur[u]; i != -1; i = nex[i])
- {
- int v = Node[i].v;
- if(d[v] == d[u] + 1 && Node[i].c> 0)
- {
- int V = dfs(v, min(Node[i].c, cap));
- Node[i].c -= V;
- Node[i ^ 1].c += V;
- ret += V;
- cap -= V;
- if(cap == 0) break;
- }
- }
- if(cap> 0) d[u] = -1;
- return ret;
- }
- int Dinic()
- {
- int ans = 0;
- while(bfs())
- {
- memcpy(cur, head, sizeof head);
- ans += dfs(s, INF);
- }
- return ans;
- }
- int main()
- {
- while(scanf("%d", &n) != EOF)
- {
- mem(head, -1);
- cnt = 0;
- int u, v;
- s = 0, t = 1000;
- rap(i, 1, n)
- {
- rd(m);
- add(s, 85 + i, 1);
- rap(j, 1, m)
- {
- rd(u), rd(v);
- add(85 + i, (u - 1) * 12 + v, 1);
- }
- }
- rap(i, 1, 85)
- add(i, t, 1);
- cout << Dinic() << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2863476.html