POJ 1637

题目大意：给出一个混合图，判断其是否存在欧拉回路

限制范围和小细节：点数在200以内，边数在1000以内，多CASE，允许存在两点间重边，保证图的连通性

很久以前从书上看到这道题，一直就想写，但是只前不太理解混合图欧拉回路的算法，这两天整理了一下最大流的模板，对混合图欧拉回路算法有了些新体会，果断把它写了，感觉很爽～

题目分析：直接说混合图欧拉回路算法啦。这里面借鉴了网络上其他人的博客

首先我们在建图的时候先将所有的无向边随便定一个方向，有向边照建，然后检查每一个节点的出入度之差（和也一样），若存在奇数，则必然不存在欧拉回路（欧拉定理证明了欧拉回路若存在，必然图中没有奇点，这一定理在混合图中同样适用。其实也不难理解，存在欧拉回路的必要条件是每个点的出入度相同，我们可以通过调整混合图的无向边的方向改变节点出入度，但是如果节点出入度之和为奇数，无论我们怎么调整它都不可能做到相等）。

初审结束后，我们就要尝试调整无向边的方向来求得这样一个欧拉回路是否真的存在。其实如果给出的图不是一个联通图，我们还需要是先进行搜索（SPFA是一个不错的选择）判断其是否联通。我们按照如下的规则构建网路：由于我们只能调整无向边，所以先忽略所有有向边。然后无向边就按我们刚刚假定的方向链接，容量为1。新建一个源点和一个汇点，将出度大于入度的点与源点相连，容量为c =（出度 - 入度）/ 2 （注：这里的出入度不要减去被我们忽略的有向边），表示我们需要调整 c 条它发出的边，再将所有入度大于出度的点连向汇点，容量为(入度 - 出度) / 2，然后求解最大流，判断是否满流，若满流则说明存在欧拉回路，且中间流满的边为我们需要调整方向的边。

其实这道题没有要求输出路径，我们可以投机取巧一下，在读入的时候不将有向边存进图里，而是只改变其起点和终点的出入度。这样省去了做网络流时重新建图的麻烦。

一下还需要说明两点：

1.是不可以将与源点汇点链接的那些点倒过来的

2.源点发出的总流量和指向汇点的边的总流量是相同的

这两个问题都是值得仔细思考和证明的，在这里就不赘述证明过程了，这两天眼睛有点累了。

  1 //date 20140115
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 const int maxn = 305;
  6 const int maxm = 5010;
  7 const int INF = 0x7FFFFFFF;
  8 
  9 inline int getint()
 10 {
 11     int ans(0); char w = getchar();
 12     while('0' > w || w > '9')w = getchar();
 13     while('0' <= w && w <= '9')
 14     {
 15         ans = ans * 10 + w - '0';
 16         w = getchar();
 17     }
 18     return ans;
 19 }
 20 
 21 inline int min(int a, int b){return a < b ? a : b;}
 22 inline int abs(int a){return a > 0 ? a : -a;}
 23 
 24 int n, m;
 25 int ind[maxn], outd[maxn];
 26 
 27 struct edge
 28 {
 29     int v, c, next;
 30 }E[maxm];
 31 int a[maxn], now[maxn];
 32 int nedge;
 33 
 34 inline void add(int u, int v, int c)
 35 {
 36     E[++nedge].v = v;
 37     E[nedge].c = c;
 38     E[nedge].next = a[u];
 39     a[u] = nedge;
 40 }
 41 
 42 int s, t;
 43 int lab[maxn];
 44 
 45 inline int label()
 46 {
 47     static int q[maxn];
 48     int l = 0, r = 1;
 49     memset(lab, 0xFF, sizeof lab);
 50     lab[s] = 0; q[1] = s;
 51     while(l < r)
 52     {
 53         int x = q[++l];
 54         for(int i = a[x]; i; i = E[i].next)
 55             if(E[i].c > 0 && lab[E[i].v] == -1){
 56                 lab[E[i].v] = lab[x] + 1;
 57                 q[++r] = E[i].v;
 58             }
 59     }
 60     //fprintf(stderr, "%d
", lab[t]);
 61     return lab[t] != -1;
 62 }
 63 
 64 int Dinic(int v, int f)
 65 {
 66     if(v == t)return f;
 67     int res = 0, w;
 68     for(int i = now[v]; i; i = now[v] = E[i].next)
 69         if((E[i].c > 0) && (f > 0) && (lab[v] + 1 == lab[E[i].v]) && (w = Dinic(E[i].v, min(f, E[i].c))))
 70         {
 71             E[i].c -= w;
 72             E[i ^ 1].c += w;
 73             res += w;
 74             f -= w;
 75         }
 76     return res;
 77 }
 78 
 79 inline int max_flow()
 80 {
 81     int ans = 0;
 82     while(label()){for(int i = 1; i <= n + 2; ++i)now[i] = a[i]; ans += Dinic(s, INF);}
 83     return ans;
 84 }
 85 
 86 int main()
 87 {
 88     int test = getint();
 89     for(int testcase = 1; testcase <= test; ++testcase)
 90     {
 91         nedge = 1;
 92         memset(E, 0, sizeof E);
 93         memset(a, 0, sizeof a);
 94         memset(ind, 0, sizeof ind);
 95         memset(outd, 0, sizeof outd);
 96         n = getint(); m = getint();
 97         int x, y, z;
 98         for(int i = 1; i <= m; ++i)
 99         {
100             x = getint(); y = getint(); z = getint();
101             if(z == 1){++outd[x]; ++ind[y];}
102             else {add(x, y, 1); add(y, x, 0); ++ind[y]; ++outd[x];}
103         }
104         s = n + 2; t = n + 1; int stat = 0;
105         int sign = 0;
106         for(int i = 1; i <= n; ++i)
107             if(abs(ind[i] - outd[i]) & 1){printf("impossible
"); sign = 1; break;}
108             else{
109                 if(ind[i] < outd[i]){add(s, i, (outd[i] - ind[i]) >> 1); add(i, s, 0);}
110                 if(ind[i] > outd[i]){add(i, t, (ind[i] - outd[i]) >> 1); add(t, i, 0); stat += ((ind[i] - outd[i]) >> 1);}
111             }
112         if(sign == 1)continue;
113         int ans = max_flow();
114         //printf("%d %d
", ans, stat);
115         if(ans == stat)printf("possible
");
116         else printf("impossible
");
117     }
118     return 0;
119 }

总结：图论中有很多有趣的性质值得仔细思考。俗话说的对啊，网络流难不在算法，而在建模，今后应该多做一些练习建模的题目。本来打算过几天总结后缀数组的……等写熟一些在说吧。转战平衡树～走起