Codeforce 847J Students Initiation
题意
给一个包含$n$($n \leq 5000$)个点的无向图,边的条数$m \leq 5000$,没有重边自环。现在给每条边一个方向,问每个点的出度的最大值,最小为多少。输出这个最小值,并输出方案。
思路&建图
- 看到最大值最小,最小值最大,首先想到炸天哥猜想:二分!!
- 二分这个最大值$mid$,检验这个猜测值是否满足要求
- 从源点相这$n$个点引一条边,容量为$mid$。
- 对于第$i$条边来说,其编号为$n+i$,从其两个断点分别引一条边到这个点,容量为$1$。再从这个点到汇点连一条边,容量为$1$。
- 跑最大流,如果最大流和边的数目相同,即这个猜测值可行。此时,对于每一条边对应的点来说,这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 5; const int maxm = 1e6; struct EDGE { int to, next, flow; EDGE(int to = 0, int next = 0, int flow = 0) : to(to), next(next), flow(flow) {} } edge[maxm]; int head[maxn], edgecnt, maxNodeNum; void init() { memset(head, -1, sizeof(head)); edgecnt = 0; maxNodeNum = 0; } void AddEdge(int s, int t, int c) { edge[edgecnt] = EDGE(t, head[s], c); head[s] = edgecnt++; edge[edgecnt] = EDGE(s, head[t], 0); head[t] = edgecnt++; maxNodeNum = max(maxNodeNum, max(s, t)); } int layer[maxn]; int p[maxn]; bool GetLayer(int st, int en) { memset(layer, 0, sizeof(int) * (maxNodeNum + 1)); layer[st] = 1; queue<int>q; q.push(st); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = edge[i].next) { if(edge[i].flow == 0) continue; int v = edge[i].to; if(layer[v]) continue; layer[v] = layer[u] + 1; q.push(v); } } return layer[en]; } int dfsFlow(int u, int en, int f) { int ret = 0; if(u == en) return f; if(layer[u] >= layer[en]) return 0; for(; ~p[u]; p[u] = edge[p[u]].next) { if(edge[p[u]].flow == 0) continue; int v = edge[p[u]].to; if(layer[v] != layer[u] + 1) continue; int temp = dfsFlow(v, en, min(f, edge[p[u]].flow)); ret += temp; f -= temp; edge[p[u]].flow -= temp; edge[p[u] ^ 1].flow += temp; if(f == 0) break; } return ret; } int dinic(int st, int en) { int ans = 0; while(GetLayer(st, en)) { memcpy(p, head, sizeof(int) * (maxNodeNum + 1)); ans += dfsFlow(st, en, INT_MAX); } return ans; } pair<int, int> E[maxn]; int n, m; bool check(int mid) { init(); for(int i = 1; i <= n; i++) AddEdge(0, i, mid); for(int i = 1; i <= m; i++) { AddEdge(E[i].first, n + i, 1); AddEdge(E[i].second, n + i, 1); } int en = n + m + 1; for(int i = n + 1; i < en; i++) AddEdge(i, en, 1); int ret = dinic(0, en); return ret == m; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++) scanf("%d %d", &E[i].first, &E[i].second); int L = 0, R = m; while(L < R) { int mid = L + R >> 1; if(check(mid)) R = mid; else L = mid + 1; } check(L); printf("%d\n", L); for(int i = 1; i <= n; i++) { for(int j = head[i]; ~j; j = edge[j].next) { if(j & 1) continue; if(edge[j].flow) continue; int eid = edge[j].to - n; int v; if(E[eid].first == i) v = E[eid].second; else v = E[eid].first; printf("%d %d\n", i, v); } } return 0; } |