Problem

模板

Solution

先随意定向，后调整。

出度 + 入度一定为偶数。

出度 > 入度则调整出边为入边，否则入边调整为出边。

需要调整的边的数目是 $\frac{| 出度 - 入度 |}{2}$。

S 向出度 > 入度连边，入度 > 出度向 T 连边（边权为需要调整的边的数目）。原图的无向边流量为 1。则每一次增广会将边反转。

若满流则有解。

Code

// Code by ajcxsu
// Problem: euler road

#include<cstdio>
#include<queue>
#include<cstring>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3e3, M=1e6, s=N-1, t=N-2;
int h[N], to[M], nexp[M], W[M], p=2;
int in[N], out[N];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
#define sins(x, y, z) ins(x, y, z), ins(y, x, 0)

queue<int> qu;
int fl[N];
bool bfs() {
    CLR(fl);
    qu.push(s), fl[s]=1;
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int u=h[na];u;u=nexp[u])
            if(W[u] && !fl[to[u]]) fl[to[u]]=fl[na]+1, qu.push(to[u]);
    }
    return fl[t];
}
int dfs(int x, int op) {
    if(x==t) return op;
    int flow=0;
    for(int u=h[x];u;u=nexp[u])
        if(W[u] && fl[to[u]]==fl[x]+1) {
            int d=dfs(to[u], min(W[u], op-flow));
            flow+=d, W[u]-=d, W[u^1]+=d;
            if(flow==op) break;
        }
    // if(!flow) fl[x]=0;
    return flow;
}

int main() {
    int T, n, m;
    gn(T);
    int u, v, w;
    char nosol=0;
    while(T--) {
        gn(n), gn(m);
        CLR(h), CLR(in), CLR(out), p=2;
        for(int i=0;i<m;i++) {
            gn(u), gn(v), gn(w), out[u]++, in[v]++;
            if(u!=v && !w) sins(u, v, 1);
        }
        nosol=0;
        int maflow=0, ans=0;
        for(int i=1;i<=n;i++) {
            if((out[i]+in[i])&1) { nosol=1; break; }
            if(out[i]>in[i]) sins(s, i, (out[i]-in[i])>>1), maflow+=(out[i]-in[i])>>1;
            else if(out[i]<in[i]) sins(i, t, (in[i]-out[i])>>1);
        }
        if(!nosol) while(bfs()) ans+=dfs(s, 0x3f3f3f3f);
        if(ans!=maflow) nosol=1;
        printf("%s\n", nosol?"impossible":"possible");
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-poj-1637.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆