poj 1966 Cable TV Network 点联通度

    求点联通度，就是求图中最大独立轨的最小值，把点拆成2个v',v''，v‘->v''容量为1,u-v的一条边就变为u''->v'和v''->u'两个容量为无穷的边，求s‘’ 到e'最大流即可

    第一次写dinic，没带当前弧优化，但对这题来说时间已经够了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
#define inf 1E9
int c[105][105],f[105][105];
int s,e;
int n;
int ans=0;
int vis[105];
int level[105];
queue<int> q;
int bfs()
{
    while(!q.empty())q.pop();
    q.push(s);
    memset(level,0,sizeof(level));
    level[s]=1;
    int u,v;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(v=0; v<n; v++)
        {
            if(!level[v]&&c[u][v]>f[u][v])
                level[v]=level[u]+1,q.push(v);
        }
    }
    return level[e];//gap
}
int dfs(int v,int flow)
{

    if(!flow)return 0;
    if(v==e)
    {
        ans+=flow;
        return flow;
    }
    int t,last=flow;
    for(int u=0; u<n; u++)
    {
        if((level[u]==level[v]+1)&&c[v][u]>f[v][u])//最短增广路
        {
            t=dfs(u,min(flow,c[v][u]-f[v][u]));
            f[v][u]+=t;
            f[u][v]-=t;
            flow-=t;
            if(!flow)break;
        }
    }
    return last-flow;
}
int main()
{
    int m;
    while(~scanf("%d%d",&n,&m))
    {
        int i,j,a,b;
        memset(c,0,sizeof(c));
        memset(f,0,sizeof(f));
        for(i=0; i<n; i++)
            c[i+n][i]=1;
        for(i=0; i<m; i++)
        {
            scanf(" (%d,%d)",&a,&b);
            c[b][a+n]=c[a][b+n]=inf;//拆点
        }
        n=n<<1;
        ans=0;
        memset(vis,0,sizeof(vis));
        int t=n/2,Max=t;
        for(i=0; i<t; i++)
            for(j=i+t+1; j<n; j++)
            {
                if(c[i][j])continue;
                memset(f,0,sizeof(f));
                e=j;
                s=i;
                ans=0;
                while(bfs())dfs(i,inf);
                Max=min(ans,Max);
            }
        printf("%d\n",Max);
    }
}