欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 1637 Sightseeing tour 混合图欧拉回路模板(不考虑不连通的情况)

程序员文章站 2022-07-10 18:12:11
...
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef int lint;
const int maxn = 10005;
const int maxm = 20005;
const lint inf = 0x3f3f3f3f;
struct dinic{
    static const int N = 10005;
    static const int M = 500005;
    static const lint inf = 0x3f3f3f3f;
    int he[N],ne[M],ver[M],d[N];
    lint edge[M];
    int s,t,tot;
    queue<int> que;
    void init( int n ){
        for( int i = 0;i <= n;i++ ){
            he[i] = 0;
        }
        tot = 1;
    }
    void add( int x,int y,lint z ){
        ver[++tot] = y; ne[ tot ] = he[x]; he[x] = tot; edge[ tot ] = z;
        ver[++tot] = x; ne[tot] = he[y]; he[y] = tot;edge[tot] = 0;
    }
    bool bfs(){
        memset( d,0,sizeof( d ) );
        while( que.size() ) que.pop();
        que.push( s );
        d[s] = 1;
        while( que.size() ){
            int x = que.front();
            que.pop();
            for( int cure = he[x];cure;cure = ne[cure] ){
                int y = ver[cure];
                if( edge[cure] && !d[y] ){
                    que.push( y );
                    d[ y ] = d[x] + 1;
                    if( y == t ) return 1;
                }
            }
        }
        return 0;
    }
    lint dfs( int x,lint flow ){
        if( x== t ) return flow;
        lint rest = flow,k;
        for( int cure = he[x];cure && rest;cure = ne[cure] ){
            int y = ver[cure];
            if( edge[cure] && d[ y ] == d[x] + 1 ){
                k = dfs( y,min( rest,edge[cure] ) );
                if( !k ) d[ y ] = 0;
                edge[cure] -= k;
                edge[ cure^1 ] += k;
                rest -= k;
            }
        }
        return flow - rest;
    }
    lint max_flow( int x,int y ){
        s = x; t = y;
        lint maxflow = 0;
        lint flow = 0;
        while( bfs() )
            while( flow = dfs( s,inf ) ) maxflow += flow;
        return maxflow;
    }
}  g;
int du[maxn],u[maxm],v[maxm],d[maxm],tot,S,T;
bool build( int m,int n ){
    tot = 0;
    g.init(T);
    for( int i = 1;i <= n;i++ ){
        du[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &d[i]);
    }
    for( int i = 1;i <= m;i++ ){
        du[ u[i] ]--;du[ v[i] ]++;
        if( d[i] != 1 ){
            g.add( v[i],u[i],1 );
        }
    }
    for( int i = 1;i <= n;i++ ){
        if( du[i]&1 ) return false;
        if( du[i] > 0 ){
            tot += du[i] / 2;
            g.add( S,i,du[i]/2 );
        }else if( du[i] < 0 ){
            g.add( i,T,-du[i]/2 );
        }
    }
    return true;
}
int main(){
    int ca;
    scanf("%d",&ca);
    while( ca-- ) {
        bool flag = true;
        int n, m;
        scanf("%d%d", &n, &m);
        S = n+2, T = n + 1;
        if(flag) {
            flag = build(m, n);
            if(!flag){
                puts("impossible");
                continue;
            }
            int res = g.max_flow(S, T);
            if (res== tot) {
                flag = true;
            } else flag = false;
        }
        if( flag ) puts("possible");
        else puts( "impossible" );
    }
    return 0;
}

 

相关标签: 网路流