Input
Output
Sample Input
4 5 8 2 1 0 1 3 0 4 1 1 1 5 0 5 4 1 3 4 0 4 2 1 2 2 0 4 4 1 2 1 2 3 0 3 4 0 1 4 1 3 3 1 2 0 2 3 0 3 2 0 3 4 1 2 0 2 3 1 1 2 0 3 2 0
Sample Output
possible impossible impossible possible
Sponsor
题目的意思是给出一张图,有有向边和无向边,稳是否存在欧拉回路
思路:
混合图的欧拉回路判定,
先把无向边随意值一个方向,判断每个点入度出度之差,若为奇数不可能。否则进行进一步判定。
你把无向边安指定的方向建图,算出每个点的入度出度,
若入度大于出度则吧源点和它相连,反之连汇点,判断是否满流
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 #include <cmath> 7 #include <map> 8 #include <set> 9 #include <stack> 10 #include <queue> 11 #include <vector> 12 #include <bitset> 13 14 using namespace std; 15 16 #define LL long long 17 const int INF = 0x3f3f3f3f; 18 #define MAXN 500 19 20 struct node 21 { 22 int u, v, next, cap; 23 } edge[MAXN*MAXN]; 24 int nt[MAXN], s[MAXN], d[MAXN], visit[MAXN]; 25 int cnt; 26 int a[2005]; 27 int b[2005]; 28 struct ed 29 { 30 int u,v,f; 31 } e[2005]; 32 33 void init() 34 { 35 cnt = 0; 36 memset(s, -1, sizeof(s)); 37 } 38 39 void add(int u, int v, int c) 40 { 41 edge[cnt].u = u; 42 edge[cnt].v = v; 43 edge[cnt].cap = c; 44 edge[cnt].next = s[u]; 45 s[u] = cnt++; 46 edge[cnt].u = v; 47 edge[cnt].v = u; 48 edge[cnt].cap = 0; 49 edge[cnt].next = s[v]; 50 s[v] = cnt++; 51 } 52 53 bool BFS(int ss, int ee) 54 { 55 memset(d, 0, sizeof d); 56 d[ss] = 1; 57 queue<int>q; 58 q.push(ss); 59 while (!q.empty()) 60 { 61 int pre = q.front(); 62 q.pop(); 63 for (int i = s[pre]; ~i; i = edge[i].next) 64 { 65 int v = edge[i].v; 66 if (edge[i].cap > 0 && !d[v]) 67 { 68 d[v] = d[pre] + 1; 69 q.push(v); 70 } 71 } 72 } 73 return d[ee]; 74 } 75 76 int DFS(int x, int exp, int ee) 77 { 78 if (x == ee||!exp) return exp; 79 int temp,flow=0; 80 for (int i = nt[x]; ~i ; i = edge[i].next, nt[x] = i) 81 { 82 int v = edge[i].v; 83 if (d[v] == d[x] + 1&&(temp = (DFS(v, min(exp, edge[i].cap), ee))) > 0) 84 { 85 edge[i].cap -= temp; 86 edge[i ^ 1].cap += temp; 87 flow += temp; 88 exp -= temp; 89 if (!exp) break; 90 } 91 } 92 if (!flow) d[x] = 0; 93 return flow; 94 } 95 96 int Dinic_flow(int ss, int ee) 97 { 98 int ans = 0; 99 while (BFS(ss, ee)) 100 { 101 for (int i = 0; i <= ee; i++) nt[i] = s[i]; 102 ans+= DFS(ss, INF, ee); 103 } 104 return ans; 105 } 106 107 int main() 108 { 109 int T; 110 int n,m; 111 for(scanf("%d",&T); T--;) 112 { 113 init(); 114 scanf("%d%d",&n,&m); 115 memset(a,0,sizeof a); 116 memset(b,0,sizeof b); 117 for(int i=0; i<m; i++) 118 { 119 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].f); 120 a[e[i].u]++,b[e[i].v]++; 121 } 122 int flag=0; 123 for(int i=1; i<=n; i++) 124 if(((int)fabs(a[i]-b[i]))%2==1) 125 { 126 flag=1; 127 break; 128 } 129 if(!flag) 130 { 131 memset(a,0,sizeof a); 132 memset(b,0,sizeof b); 133 for(int i=0; i<m; i++) 134 { 135 if(e[i].f==0) 136 add(e[i].u,e[i].v,1); 137 138 a[e[i].u]++,b[e[i].v]++; 139 } 140 int ct=0; 141 for(int i=1; i<=n; i++) 142 if(a[i]<b[i]) 143 add(i,n+1,(b[i]-a[i])/2); 144 else if(a[i]>b[i]) 145 add(0,i,(a[i]-b[i])/2),ct+=(a[i]-b[i])/2; 146 if(ct!=Dinic_flow(0,n+1)) 147 flag=1; 148 } 149 if(flag) 150 printf("impossible\n"); 151 else 152 printf("possible\n"); 153 } 154 return 0; 155 }
原文:https://www.cnblogs.com/csx-zzh/p/14499255.html