最小路径覆盖问题【网络流24题】

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 2e4 + 7;
 49 
 50 int s, t, cnt;
 51 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1], vis[maxn << 1];
 52 int w[maxn << 1];//残量网络
 53 int rev[maxn << 1];
 54 int depth[maxn << 1];//图层
 55 int n, m;
 56 
 57 void BuildGraph(int u, int v, int cap) {
 58     ++cnt;
 59     edge[cnt] = v;
 60     nxt[cnt] = head[u];
 61     rev[cnt] = cnt + 1;
 62     w[cnt] = cap;
 63     head[u] = cnt;
 64 
 65     ++cnt;
 66     edge[cnt] = u;
 67     nxt[cnt] = head[v];
 68     w[cnt] = 0;
 69     rev[cnt] = cnt - 1;
 70     head[v] = cnt;
 71 }
 72 
 73 bool bfs(int x) {
 74     queue<int> q;
 75     while(!q.empty()) {
 76         q.pop();
 77     }
 78     memset(depth, 63, sizeof(depth));
 79     depth[s] = 0;
 80     q.push(s);
 81     do {
 82         int u = q.front();
 83         q.pop();
 84         for ( int i = head[u]; i; i = nxt[i] ) {
 85             int v = edge[i];
 86             if(w[i] > 0 && depth[u] + 1 < depth[v]) {
 87                 depth[v] = depth[u] + 1;
 88                 q.push(v);
 89                 if(v == t) {
 90                     return true;
 91                 }
 92             }
 93         }
 94     } while (!q.empty());
 95     return false;
 96 }
 97 
 98 int dfs(int u, int dist) {
 99     if(u == t) {
100         return dist;
101     }
102     for ( int i = head[u]; i; i = nxt[i] ) {
103         int v = edge[i];
104         if(depth[v] == depth[u] + 1 && w[i] > 0) {
105             int di = dfs(v, min(dist, w[i]));
106             if(di > 0) {
107                 w[i] -= di;
108                 w[rev[i]] += di;
109                 vis[u] = v;
110                 //printf("vis[%d]:%d\n",u, v);
111                 return di;
112             }
113         }
114     }
115     return 0;
116 }
117 
118 int main()
119 {
120     //freopen("data.txt", "r", stdin);
121     memset(vis, 0, sizeof(vis));
122     read(n); read(m);
123     s = 0, t = 2 * n + 1;
124     for ( int i = 1; i <= m; ++i ) {
125         int u, v;
126         read(u); read(v);
127         BuildGraph(u, v + n, 1);
128     }
129     for ( int i = 1; i <= n; ++i ) {
130         BuildGraph(s, i, 1);
131         BuildGraph(n + i, t, 1);
132     }
133     int ans = 0;
134     while(bfs(s)) {
135         //cout << "!" << endl;
136         int res = dfs(0, 0x7f7f7f7f);
137         ans += res;
138     }
139     for ( int i = 1; i <= n; ++i ) {
140         if(vis[i]) {
141             int temp = i;
142             do {
143                 if(temp > n) {
144                     temp -= n;
145                 }
146                 printf("%d ",temp);
147                 int x = vis[temp];
148                 vis[temp] = 0;
149                 temp = x;
150             } while (temp != 0);
151             puts("");
152         }
153     }
154     printf("%d\n",n - ans);
155     return 0;
156 }