| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
请大神们帮我看一下我的临界表到底拿错了?我该神邻接矩阵周,其他大框架基本没动,就AC了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator