Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

走投无路,只能贴代码了

Posted by E09610125 at 2010-07-13 09:39:00 on Problem 1087
In Reply To:我就是这样建的图啊,思路一样,死都过不了 Posted by:E09610125 at 2010-07-13 09:11:28
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 815
#define INF 1000000000
using namespace std;
int cap[N][N],flow[N][N],p[N],lim[N];
queue<int>q;
int mf(int s,int t)
{
    memset(flow,0,sizeof(flow));
    int f=0;
    while(1)
    {
        memset(lim,0,sizeof(lim));
        lim[s]=INF;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int v=0;v<=t;v++) if(!lim[v]&&cap[u][v]>flow[u][v])
            {
                p[v]=u;q.push(v);
                lim[v]=lim[u] < cap[u][v]-flow[u][v] ? lim[u] : cap[u][v]-flow[u][v];
            }
        }
        if(lim[t]==0) break;
        for(int u=t;u!=s;u=p[u])
        {
            flow[p[u]][u]+=lim[t];
            flow[u][p[u]]-=lim[t];
        }
        f+=lim[t];
    }
    return f;
}
char rec[815][30],de[30];
int main()
{
    int n,m,k;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        memset(cap,0,sizeof(cap));
        for(i=1;i<=n;i++)
        {
            scanf("%s",rec[i]);
            cap[0][i]=1;
        }
        scanf("%d",&m);
        int top=n+1;
        for(i=1;i<=m;i++)
        {
            scanf("%s %s",de,rec[top]);
            bool find=0;
            for(j=1;j<top;j++)
                if(strcmp(rec[top],rec[j])==0) {find=1;cap[j][i]=INF;break;}
            if(!find) {cap[top][i]=INF;top++;}
        }
        scanf("%d",&k);
        char ma[30],re[30];
        int s1,e;
        for(i=0;i<k;i++)
        {
            scanf("%s %s",ma,re);
            int find=0;
            for(j=1;j<top;j++)
                if(strcmp(rec[j],re)==0) {find=1;s1=j;break;}
            if(!find) {strcpy(rec[top],re);s1=top++;}
            for(find=0,j=1;j<top;j++)
                if(strcmp(ma,rec[j])==0)  {find=1;e=j;break;}
            if(!find) {strcpy(rec[top],ma);e=top++;}
            cap[s1][e]=INF;
        }
        for(i=1;i<=m;i++)
            cap[i][top]=1;
        int ans=m-mf(0,top);
        printf("%d\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator