poj1637混合欧拉回路的判定

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 200+10;
int n, m;   //n个顶点  m条边
int in[200+5], out[200+5];

struct Dinic
{
    int n;       //n个顶点
    struct edge
    {
        int from, to, cap;
    };
    vector<int> G[maxn];
    vector e;
    int level[maxn], iter[maxn];

    void init()
    {
        for(int i=0; i<=n; i++) G[i].clear();
        e.clear();
    }

    void add_edge(int u, int v, int cap)
    {
        e.push_back((edge){u, v, cap});
        e.push_back((edge){v, u, 0});
        int m = e.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }

    void bfs(int s)
    {
        memset(level, -1, sizeof(level));
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty())
        {
            int u = que.front();
            que.pop();
            for(int i=0; i)
            {
                edge &te = e[G[u][i]];
                if(te.cap>0 && level[te.to]<0)
                {
                    level[te.to] = level[u] + 1;
                    que.push(te.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f)
    {
        if(v == t) return f;
        for(int &i=iter[v]; i)
        {
            edge &tpe = e[G[v][i]];
            if(tpe.cap>0 && level[v]<level[tpe.to])
            {
                int d = dfs(tpe.to, t, min(f, tpe.cap));
                if(d > 0)
                {
                    tpe.cap -= d;
                    e[G[v][i]^1].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) return flow;
            memset(iter, 0, sizeof(iter));
            int f;
            while((f=dfs(s, t, 0x3fffffff)) > 0)
                flow += f;
        }
    }
} di;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);   //0超级源点  n+1超级汇点
        di.n = n+2;
        di.init();
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        for(int i=0; i)
        {
            int u, v, t;
            scanf("%d%d%d", &u, &v, &t);
            in[v]++; out[u]++;
            if(t == 0)  di.add_edge(u, v, 1);
        }
        bool flog = true;
        for(int i=1; i<=n&&flog; i++)
            if(abs(in[i]-out[i])%2 != 0) flog=false;
        if(!flog)
        {
            printf("impossible\n");
            continue;
        }
        for(int i=1; i<=n; i++)
        {
            if(in[i]<out[i])
                di.add_edge(0, i, (out[i]-in[i])/2);
            else if(in[i]>out[i])
                di.add_edge(i, n+1, (in[i]-out[i])/2);
        }
        di.max_flow(0, n+1);
        flog = true;
        for(int i=0; i2)
        {
            if(di.e[i].from==0 && di.e[i].cap!=0) flog=false;
        }
        if(flog) printf("possible\n");
        else printf("impossible\n");
    }
    return 0;
}