|
|
 #include <iostream>
using namespace std;
const int maxn=200;
const int INF=1000000;
int g[maxn][maxn];
int f[maxn][maxn];
int r[maxn][maxn];
int Edmonds_Karp(int n,int g[][maxn],int s,int t,int f[][maxn])
   {
 int i,j,k,c,head,tail,flow=0 ;
int prev[maxn],visit[maxn],q[maxn];
for(i=0;i<n;i++)for(j=0;j<n;j++)
  {
f[i][j]=0 ;
r[i][j]=g[i][j];
 }
while(1)
{
head=tail=0 ;
memset(visit,0,sizeof(visit));
q[tail++]=s ;
prev[s]=-1 ;
visit[s]=1 ;
while(head<tail)
{
k=q[head++];
for(i=0;i<n;i++)
if(!visit[i]&&r[k][i]>0)
{
visit[i]=1 ;
prev[i]=k ;
if(i==t)goto next ;
q[tail++]=i ;
}
}
next :
if(!visit[t])break ;
for(c=INT_MAX,j=t;j!=s;j=i)
{
i=prev[j];
if(c>r[i][j])c=r[i][j];
}
for(j=t;j!=s;j=i)
{
i=prev[j];
f[i][j]+=c ;
f[j][i]=-f[i][j];
r[i][j]=g[i][j]-f[i][j];
r[j][i]=g[j][i]-f[j][i];
}
flow+=c ;
}
return flow ;
 }
void Floyd(int n,int map[][maxn])
{
int i,j,k;
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
int mat[maxn][maxn];
int tmp[maxn][maxn];
int mp[maxn][maxn];
int make[maxn][maxn];
int bus[maxn];
void build(int id)
{
int i,j;
for(i=0;i<id;i++){
make[i][i+id]=1;
for(j=0;j<id;j++){
if(mp[i][j])
make[i+id][j]=INF;
}
}
}
int main()
{
int n,m,p;
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
if(n==0&&m==0&&p==0)break;
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
mat[i][j]=INF;
}
mat[i][i]=0;
}
for(i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
--u;--v;
mat[u][v]=1;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
tmp[i][j]=mat[i][j];
}
}
Floyd(n,tmp);
if(p<tmp[0][n-1])
{
printf("0\n");
continue;
}
int id=0;
for(i=0;i<n;i++){
if(tmp[0][i]+tmp[i][n-1]<=p){
bus[id++]=i;
}
}
for(i=0;i<id;i++){
for(j=0;j<id;j++){
mp[i][j]=0;
if(mat[bus[i]][bus[j]]==1)
mp[i][j]=1;
}
}
build(id);
printf("%d\n",Edmonds_Karp(2*id,make,id,id-1,f));
}
return 0;
}
|