PKU 3921-Destroying the bus stations

6/15のICPC練習会で出た問題

問題概要

N個の頂点を持つ有向グラフが与えられる．
頂点1から頂点Nに向かう長さがK以下のルートを全て無くすには何個頂点を消せば良いか

解法

K以内に行ける辺を全てリストアップし，そのグラフ上で最大流を行なう．
頂点消去なので頂点の流量を1にする．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
using namespace std;

typedef int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
const lli INF=1LL<<28;
lli dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
const lli MAX_V=250;
struct edge{lli to,cap,rev;};
int V;
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(lli from,lli to,lli cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

lli dfs(lli v,lli t,lli f){
	if(v==t)return f;
	used[v]=true;
	for(lli i=0;i<(lli)G[v].size();i++){
		edge &e=G[v][i];
		if(!used[e.to]&&e.cap>0){
			lli d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
lli max_flow(lli s,lli t){
	lli flow=0;
	for(;;){
		memset(used,0,sizeof(used));
		lli f=dfs(s,t,INF);
		if(f==0)return flow;
		flow+=f;
	}
}
int n,m,K;
int main(){
	for(;cin>>n>>m>>K;){
		if(n==0&&m==0&&K==0)break;
		int V[50][50],dist[50][50];
		REP(i,n)REP(j,n)V[i][j]=INF;
		for(int i=0;i<m;i++){
			int s,f;
			cin>>s>>f;
			s--;f--;
			V[s][f]=1;
		}
		REP(i,n)V[i][i]=0;
		REP(i,n)REP(j,n){
			dist[i][j]=V[i][j];
		}
		REP(k,n)REP(i,n)REP(j,n){
			V[i][j]=min(V[i][j],V[i][k]+V[k][j]);
		}
		for(int i=0;i<2*n;i++){
			G[i].clear();
		}
		REP(i,n)REP(j,n){
			if(V[0][i]+1+V[j][n-1]<=K&&dist[i][j]==1){
				add_edge(i*2+1,j*2,INF);
			}
		}
		REP(i,n){
			if(i==0||i==n-1){
				add_edge(i*2,i*2+1,INF);
			}else{
				add_edge(i*2,i*2+1,1);
			}
		}
		cout<<max_flow(0,n*2-1)<<endl;
	}
	return 0;
}