poj 1966 Cable TV Network

#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
const int maxn=109,inf=1e8;  
int n,m;  
int a[maxn][maxn];  
int que[maxn],level[maxn];  
int head[maxn],lon;  
struct  
{  
    int next,to,c;  
}e[maxn*maxn<<1];  
  
void edgeini()  
{  
    memset(head,-1,sizeof(head));  
    lon=-1;  
}  
void edgemake(int from,int to,int c)  
{  
    e[++lon].c=c;  
    e[lon].to=to;  
    e[lon].next=head[from];  
    head[from]=lon;  
}  
  
int makelevel(int s,int t)  
{  
    memset(level,0,sizeof(level));  
    int front=1,end=0;  
    que[++end]=s;  
    level[s]=1;  
    while(front<=end)  
    {  
        int u=que[front++];  
        if(u==t) return true;  
        for(int k=head[u];k!=-1;k=e[k].next)  
        {  
            int v=e[k].to;  
            if(!level[v]&&e[k].c)  
            {  
                que[++end]=v;  
                level[v]=level[u]+1;  
            }  
        }  
    }  
    return false;  
}  
  
int dfs(int now,int t,int maxf)  
{  
    if(now==t) return maxf;  
    int ret=0;  
    for(int k=head[now];k!=-1;k=e[k].next)  
    {  
        int u=e[k].to;  
        if(e[k].c&&level[u]==level[now]+1)  
        {  
            int f=dfs(u,t,min(maxf-ret,e[k].c));  
            e[k].c-=f;  
            e[k^1].c+=f;  
            ret+=f;  
            if(ret==maxf) return ret;  
        }  
    }  
    return ret;  
}  
  
int maxflow(int s,int t)  
{  
    int ret=0;  
    while(makelevel(s,t))  
    {  
        ret+=dfs(s,t,inf);  
    }  
    return ret;  
}  
  
int solve(int s,int t)  
{  
    edgeini();  
    for(int i=1;i<=n;i++)  
    for(int j=i+1;j<=n;j++)  
    if(a[i][j])  
    {  
        edgemake(i*2,j*2-1,inf);  
        edgemake(j*2-1,i*2,0);  
        edgemake(j*2,i*2-1,inf);  
        edgemake(i*2-1,j*2,0);  
    }  
  
    for(int i=1;i<=n;i++)  
    {  
        edgemake(i*2,i*2-1,1);  
        edgemake(i*2-1,i*2,1);  
    }  
  
    return maxflow(s*2,t*2-1);  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        memset(a,0,sizeof(a));  
        for(int i=1,from,to;i<=m;i++)  
        {  
            char tmp;  
            while(scanf("%c",&tmp),tmp!='(') ;  
            scanf("%d",&from);  
            while(scanf("%c",&tmp),tmp!=',') ;  
            scanf("%d",&to);  
            while(scanf("%c",&tmp),tmp!=')') ;  
            from++,to++;  
            a[from][to]=a[to][from]=1;  
        }  
        int ans=n;  
  
        for(int i=1;i<=n;i++)  
        for(int j=i+1;j<=n;j++)  
        ans=min(ans,solve(i,j));  
        cout<<ans<<endl;  
    }  
    return 0;  
}