HDU2485Destroying the bus stations 拆点网络流求割点个数

时间:2022-05-19 21:56:31

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2485

题目要求:删除最少的点,使得源点到汇点的距离大于k

思路:拆点、建图求费用小于等于k的最大流

#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <queue>
using namespace std;
#define min(x,y) (x)<(y)?(x):(y)
const int maxm = 10005;
const int maxn = 1100; struct node{
int v,flow,cost,next;
}edge[maxm];
int head[maxn],dis[maxn],vis[maxn],pre[maxn],cur[maxn];
int id,n,m,k;
int sink,source;
void add_edge(int u,int v,int flow,int cost){
edge[id].v = v;edge[id].cost = cost;edge[id].flow = flow;edge[id].next = head[u];head[u] = id++;
edge[id].v = u;edge[id].cost = -cost;edge[id].flow = 0 ;edge[id].next = head[v];head[v] = id++;
}
void init(){
int u,v,i;
source = 1,sink = n*2;
memset(head,-1,sizeof(head));id = 0;
for( i = 1; i <= m; i++){
scanf("%d%d",&u,&v);
add_edge(u+n,v,1,1);
}
for( i = 2; i < n; i++)//拆点
add_edge(i,i+n,1,0);
add_edge(1,n+1,5000000,0);
add_edge(n,n+n,5000000,0);
} int spfa(){
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
pre[source] = source;
dis[source] = 0;
vis[source] = 1;
queue<int>que;
que.push(source);
while( !que.empty()){
int u = que.front();
que.pop();
vis[u] = 0;
for(int id = head[u]; id != -1; id = edge[id].next){
int v = edge[id].v;
if(edge[id].flow > 0 && (dis[v] == -1 || dis[v] > dis[u] + edge[id].cost )){
dis[v] = dis[u] + edge[id].cost;
pre[v] = u;cur[v] = id;
if(!vis[v] ){
vis[v] = 1;
que.push(v);
}
}
}
}
if(dis[sink] == -1 || dis[sink] > k)return 0;
return 1;
} int get_max(){
int max_flow = 0;
while(spfa())
{
//cout << dis[sink] << endl;
max_flow += 1;
int now = sink;
while(now != source){
edge[cur[now]].flow -= 1;
edge[cur[now]^1].flow += 1;
now = pre[now];
}
}
return max_flow;
}
int main(){
freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&m,&k),n||m||k){
init();
printf("%d\n",get_max());
}
return 0;
}