In the Middle Ages m European cities imported many goods from n Arabian cities. Due to continous feudal wars, European cities did not trade with each other, so is some European city needed some Arabian goods, the special trade route was established for this particular trade.
Studying the manuscripts historians have found out that each European city imported goods from at least two Arabian cities, and each Arabian city exported goods to at least two European cities. They have also investigated different factors and identified all potential trade routes (trade routes between some pairs of cities were impossible due to various reasons).
Now historians wonder, what is the minimal possible number of trade routes, that could have existed. Help them to find that out.
Input
The first line of the input file contains m, n, and p - the number of European and Arabian cities respectively, and the number of potential trade routes (1 <= m, n <= 300, 1 <= p <= nm). The following p lines describe potential trade routes, each description consists of two numbers - the European and the Arabian city connected by the route.
Output
On the first line of the output file print k - the minimal possible number of trade routes that could have existed. After that output k numbers - some minimal set of routes that might have existed to satisfy all conditions. Routes are numbered starting from 1 as they are given in the input file.
If historians must have made a mistake and it is impossible to satisfy the specified conditions, print -1 on the first and the only line of the output file.
Sample Input
5 5 14 1 2 1 3 1 4 1 5 2 1 2 5 3 1 3 5 4 1 4 5 5 1 5 2 5 3 5 4
Sample Output
12 1 2 3 5 6 7 8 9 10 12 13 14
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 1010; 5 struct arc{ 6 int to,flow,next; 7 arc(int x = 0,int y = 0,int z = -1){ 8 to = x; 9 flow = y; 10 next = z; 11 } 12 }e[500010]; 13 int head[maxn],cur[maxn],d[maxn],du[maxn],tot; 14 void add(int u,int v,int flow){ 15 e[tot] = arc(v,flow,head[u]); 16 head[u] = tot++; 17 e[tot] = arc(u,0,head[v]); 18 head[v] = tot++; 19 } 20 bool bfs(int S,int T){ 21 queue<int>q; 22 memset(d,-1,sizeof d); 23 d[S] = 1; 24 q.push(S); 25 while(!q.empty()){ 26 int u = q.front(); 27 q.pop(); 28 for(int i = head[u]; ~i; i = e[i].next){ 29 if(e[i].flow && d[e[i].to] == -1){ 30 d[e[i].to] = d[u] + 1; 31 q.push(e[i].to); 32 } 33 } 34 } 35 return d[T] > -1; 36 } 37 int dfs(int u,int T,int low){ 38 if(u == T) return low; 39 int a,tmp = 0; 40 for(int &i = cur[u]; ~i; i = e[i].next){ 41 if(e[i].flow && d[e[i].to] == d[u] +1&&(a=dfs(e[i].to,T,min(e[i].flow,low)))){ 42 e[i].flow -= a; 43 e[i^1].flow += a; 44 low -= a; 45 tmp += a; 46 if(!low) break; 47 } 48 } 49 if(!tmp) d[u] = -1; 50 return tmp; 51 } 52 int dinic(int S,int T,int ret = 0){ 53 while(bfs(S,T)){ 54 memcpy(cur,head,sizeof head); 55 ret += dfs(S,T,INF); 56 } 57 return ret; 58 } 59 int main(){ 60 int n,m,p,u,v; 61 while(~scanf("%d%d%d",&n,&m,&p)){ 62 memset(head,-1,sizeof head); 63 memset(du,0,sizeof du); 64 int S = tot = 0,T = n + m + 1,SS = T + 1,TT = SS + 1; 65 for(int i = 0; i < p; ++i){ 66 scanf("%d%d",&u,&v); 67 add(u,v + n,1); 68 } 69 for(int i = 1; i <= n; ++i){ 70 add(S,i,INF); 71 du[S] -= 2; 72 du[i] += 2; 73 } 74 for(int i = 1; i <= m; ++i){ 75 add(i + n,T,INF); 76 du[i + n] -= 2; 77 du[T] += 2; 78 } 79 int sum = 0; 80 for(int i = S; i <= T; ++i){ 81 if(du[i] > 0){ 82 add(SS,i,du[i]); 83 sum += du[i]; 84 }else add(i,TT,-du[i]); 85 } 86 u = dinic(SS,TT); 87 add(T,S,INF); 88 if(u + dinic(SS,TT) == sum){ 89 bool flag = false; 90 printf("%d\n",e[tot-1].flow); 91 for(int i = 0; i < p; ++i) 92 if(!e[i*2].flow){ 93 if(flag) putchar(‘ ‘); 94 flag = true; 95 printf("%d",i + 1); 96 } 97 puts(""); 98 }else puts("-1"); 99 } 100 return 0; 101 }
原文：http://www.cnblogs.com/crackpotisback/p/4859237.html
