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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

请大神们帮我看一下我的临界表到底拿错了?我该神邻接矩阵周,其他大框架基本没动,就AC了

Posted by cangqiongzhiding at 2018-10-01 11:02:35 on Problem 3281
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int n,f,d;
int liu[405][405];
int depth[405],s=0,t=403;
vector<int>p[405];
int mins(int x,int y)
{
    return (x<y)?x:y;
}
bool bfs()
{
    //cout<<16<<endl;
    int que[409],head=1,tail=1;
    memset(depth,0,sizeof(depth));
    que[tail++]=s;
    depth[s]=1;
    while(head<tail)
    {
        //cout<<23<<endl;
        for(int i=0;i<p[que[head]].size();i++)
        {
            int u=que[head],v=p[que[head]][i];
            if(liu[u][v]>0&&depth[v]==0)
            {
                que[tail++]=v;
                depth[v]=depth[u]+1;
            }
        }
        head++;
    }
    if(depth[t]==0)
        return 0;
    //cout<<37<<endl;
    return 1;
}
int dfs(int x,int y)
{
    //cout<<38<<endl;
    if(x==t)
        return y;
    for(int i=0;i<p[x].size();i++)
    {
        int v=p[x][i];
        if(liu[x][v]>0&&depth[v]==depth[x]+1)
        {
            cout<<v<<endl;
            int di=dfs(v,mins(liu[x][v],y));
            if(di>0)
            {
                liu[x][v]-=di;
                liu[v][x]+=di;
                return di;
            }
        }
    }
    return 0;
}
int main()
{
    int ans=0;
    cin>>n>>f>>d;
   // cout<<s<<t<<endl;
    memset(liu,0,sizeof(liu));
    for(int i=1;i<=n;i++)
    {
        int f1,d1;
        scanf("%d%d",&f1,&d1);
        p[i].push_back(i+300);
        liu[i][i+300]=1;
        for(int j=1;j<=f1;j++)
        {
            int x;
            scanf("%d",&x);
            p[100+x].push_back(i);
            liu[100+x][i]=1;
        }
        for(int k=1;k<=d1;k++)
        {
            int x;
            scanf("%d",&x);
            p[i+300].push_back(x+200);
            liu[i+300][x+200]=1;
        }
    }
    //cout<<85<<endl;
    for(int i=1;i<=f;i++)
    {
        p[s].push_back(100+i);
        liu[s][100+i]=1;
    }
    //cout<<92<<endl;
    for(int i=1;i<=d;i++)
    {
        p[i+200].push_back(t);
        liu[i+200][t]=1;
    }
    //cout<<98<<endl;
    while(bfs())
    {
        while(int t=dfs(s,99999))
        {
            ans+=t;
        }
    }
    cout<<ans<<endl;
    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