# Bzoj2324 [zjoi2011]营救皮卡丘

Posted by yjjr's blog on February 6, 2018

# 题目

Description

K个人是可以分头行动的，只要有任何一个人在K-1号据点被摧毁之后，经过K号据点，K号据点就被摧毁了。显然的，只要N号据点被摧毁，皮卡丘就得救了。

Input

0 1 1

1 2 1

2 3 100

0 3 1 Sample Output 3

【样例说明】

Source

Day2

# 分析

i’->j流量1费用dis[i][j]

S->i’流量1费用0

i->T流量1费用0

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define inf 1000000000
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=306,maxm=1e5+6;
int S,T,ans,n,m,k,cnt=1,dis[maxn][maxn],que[maxm],d[maxn],last[maxn];
bool inq[maxn];
struct edge{int to,next,v,c;}e[maxm];

void insert(int u,int v,int w,int c){
e[++cnt]=(edge){v,last[u],w,c};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0,-c};last[v]=cnt;
}

void floyd()
{
rep(K,0,n)
rep(i,0,n)
rep(j,0,n)
if((K<=i||K<=j)&&dis[i][j]>dis[i][K]+dis[K][j])dis[i][j]=dis[i][K]+dis[K][j];
}

bool spfa()
{
mem(inq,0);
rep(i,0,T)d[i]=inf;
que[0]=T;d[T]=0;inq[T]=1;
reg(now)
if(e[i^1].v&&d[now]-e[i].c<d[e[i].to]){
d[e[i].to]=d[now]-e[i].c;
if(!inq[e[i].to])inq[e[i].to]=1,que[tail++]=e[i].to;
}
inq[now]=0;
}
if(d[S]!=inf)return 1;else return 0;
}

int dfs(int x,int f)
{
inq[x]=1;if(x==T)return f;
int used=0,w;
reg(x)
if(!inq[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to]){
w=f-used;w=dfs(e[i].to,min(e[i].v,w));
ans+=w*e[i].c;
e[i].v-=w;e[i^1].v+=w;
used+=w;if(used==f)return f;
}
return used;
}

void zkw()
{
while(spfa()){
//cout<<"R";
inq[T]=1;
while(inq[T]){mem(inq,0);dfs(S,inf);}
}
}
int main()
{
S=2*n+2,T=S+1;
rep(i,0,n)
rep(j,0,n)
if(i!=j)dis[i][j]=inf;
rep(i,1,m){
dis[u][v]=dis[v][u]=min(dis[u][v],w);
}
floyd();
rep(i,1,n){
insert(S,i+n+1,1,0);
insert(i,T,1,0);
}
insert(S,n+1,k,0);
rep(i,0,n)
rep(j,i+1,n)
if(dis[i][j]!=inf)insert(i+n+1,j,1,dis[i][j]);
zkw();
cout<<ans<<endl;
return 0;
}