【POJ 1637】Sightseeing tour 混合圖歐拉回路 最大流

題意就是求混合圖的歐拉回路是否存在。

題中說明了是連通圖，并且任意一點都可由其它點達到。是以，不必再判斷連通性了，直接最大流就OK.

看了看黑書，沒看懂，看了看網上的解釋，依然沒看懂。。

後來，隻好自己想啊想，想啊想，終于給A了。。

我是先把每個邊都當成向邊判斷是否存在奇度頂點，如果存在肯定不存在歐拉回路了。

同時用一個數組d2隻統計有向邊擷取每個點的有向的度（出度記為正，入度記為負）。

然後，建立出如下的圖：

源->出度大于入度的點->所有頂點->入度大于出度的點->彙。

其中，源到出度大于入度的點的邊容量是上面那個數組裡統計出的有向的度值，入度大于出度的點的點到彙的容量也是那個度數（當然要取個相反數）。除此之外，再把所有的無向邊都加到圖裡，正反邊容量都設定成兩個點之間的無向邊的條數（都是正的）。

然後求出最大流流值，判斷其是否等于所有出度大于入度的點的度數之和（即d2中大于0的數的和）。

直接用了以前寫的SAP模闆

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<functional>

using namespace std;

const int MAX=210;

int degree[MAX],d2[MAX];

#define CLR(arr,val) memset(arr,val,sizeof(arr))

const int INF=1000000000;

template<int MAX>

class SapMaxFlow

{

public:

int cap[MAX][MAX],h[MAX],flow[MAX][MAX];// cap表示容量矩陣，需要是0序圖 h表示到彙點的距離

int v;//v表示包括源與彙的所有結點的數量

int GetMaxFlow(int s,int t)

{

int total_flow=0;

init(t);

int cur = s, i;

CLR(low,0);

while(h[s] < v)

{

low[s] = INF;

for(i = 0; i != v; i++)

if(cap[cur][i] - flow[cur][i] > 0 && h[cur] == h[i] + 1) //如果找到允許弧

{

low[i] = min(cap[cur][i] - flow[cur][i], low[cur]);

pre[i] = cur;

cur = i;

if(cur == t) //找到一條最短增廣路

{

total_flow += low[t];

while(cur != s)

{

flow[pre[cur]][cur]+=low[t];

flow[cur][pre[cur]]-=low[t];

cur=pre[cur];

}

CLR(low,0);

}

break;

}

if(i == v) //如果沒有找到允許弧

{

int minh=INF;

for(int j = 0; j != v; j++)

if(cap[cur][j] - flow[cur][j] > 0 && minh > h[j]+1)

minh=h[j]+1;

h[cur]=minh;

if(cur != s) cur = pre[cur];

}

}

return total_flow;

}

private:

int q[MAX],low[MAX],pre[MAX];

void init(int t)

{

int head = 0, tail = 0, cur;

CLR(h,0);

q[++tail]=t;

while(head < tail)

{

cur=q[++head];

for(int i=0;i!=v;i++) if(!h[i] && cap[i][cur]-flow[i][cur]>0) //由于可能由初始流，是以減去flow[i][cur]

q[++tail]=i,h[i]=h[cur]+1;

}

}

};

SapMaxFlow<MAX> g;

bool isodd(int n)

{

return n&1;

}

int main()

{

//freopen("in.txt","r",stdin);

int n,v,e,a,b,l,cnt;

scanf("%d",&n);

while(n--)

{

cnt=0;

CLR(g.cap,0);

CLR(g.flow,0);

CLR(degree,0);

CLR(d2,0);

scanf("%d%d",&v,&e);

for(int i=0;i!=e;i++)

{

scanf("%d%d%d",&a,&b,&l);

++degree[a-1];

++degree[b-1];

if(l)

{

d2[a-1]++;

d2[b-1]--;

}

else

{

++g.cap[a-1][b-1];

++g.cap[b-1][a-1];

}

}

if(find_if(degree,degree+v,isodd)!=degree+v) { puts("impossible"); continue;}

int s=v,t=v+1,n=v+2;

for(int i=0;i!=v;i++)

{

if(d2[i]>0) { g.cap[s][i]=d2[i];cnt+=d2[i];}

else if(d2[i]<0) g.cap[i][t]=-d2[i];

}

g.v=n;

puts(g.GetMaxFlow(s,t)==cnt?"possible":"impossible");

}

}