2018 Benelux Algorithm Programming Contest (BAPC 18) I.In Case of an Invasion, Please...(网络流+最短路)

题目

思路来源

http://blog.leanote.com/post/icontofig/e6b30008ad99

题解

怎么会不觉得自己sb呢，本来是很裸的网络流题

预处理最短路，每个点到避难所的距离

挑战原题的思路，首先二分最小时间t，每个居民只能去小于等于t的避难所，

于是就变成一个匹配问题，类似地跑网络流，

左源右汇，中间两层，一层是实际的点，一层是避难所

但是1e5个点，乘上二分的复杂度会t

注意到避难所只有10个，所以可以把到避难所连通性相同的点合并到一起，

这样实际的点就只有1<<10个了

注意到答案一定是最短路的每个时间，所以可以离散化这个时间，

从而二分最短路数组中的值，减小常数

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
typedef pair<int,int> P;
const ll inf=0x3f3f3f3f3f3f3f3fll;
const int INF=0x3f3f3f3f,maxn=1e5+10,maxm=2e6+4e5+10,M=(1<<10)+5;
int level[maxn],p[maxn];
ll dis[11][maxn],d[maxm],all,c;
bool vis[maxn];
int head[maxn],cnt;
int n,m,s,up[maxn];
int st[maxn];//state
ll sum[M];
struct node{
	ll v;
	int id;
	bool operator<(const node &x)const{
		return v>x.v;
	}
};
struct edge{
	int v,nex;
	ll w;
}e[maxm];
void init(){
	cnt=0;
	memset(head,-1,sizeof head);
	memset(sum,0,sizeof sum);
}
void add(int u,int v,ll w){
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op) {
	add(u,v,w);
	add(v,u,op?0:w);
}
void dijkstra(int x,int s){
	memset(vis,0,sizeof vis);
	priority_queue<node>q;
	q.push(node{0,s});
	dis[x][s]=0;
	while(!q.empty()){
		node y=q.top();
		q.pop();
		d[++c]=y.v;
		int id=y.id;
		if(vis[id])continue;
		vis[id]=1;
		for(int i=head[id];~i;i=e[i].nex){
			int to=e[i].v;ll w=e[i].w;
			if(dis[x][to]>dis[x][id]+w){
				dis[x][to]=dis[x][id]+w;
				q.push(node{dis[x][to],to});
			}
		}
	}
}
bool bfs(int s,int t){
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex){
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w){
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t){
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex){
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w){
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t){
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
bool ok(ll x){
	init();
	for(int j=1;j<=n;++j){
		st[j]=0;
		for(int i=1;i<=s;++i){
			if(dis[i][j]>x)continue;
			st[j]|=(1<<(i-1));
		}
		sum[st[j]]+=p[j];
	}
	int mx=1<<s;
	int st=mx+s+1,ed=mx+s+2;
	for(int i=0;i<mx;++i){
		if(!sum[i])continue;
		add2(st,i,sum[i],1);
		for(int j=0;j<s;++j){
			if(i>>j&1){
				add2(i,mx+j+1,sum[i],1);
			}
		}
	}
	for(int i=1;i<=s;++i){
		add2(mx+i,ed,up[i],1);
	}
	return Dinic(st,ed)==all;
}
int main(){ 
	init();
	memset(dis,inf,sizeof dis);
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		all+=p[i];
	}
	while(m--){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add2(x,y,w,0);
	}
	for(int i=1;i<=s;++i){
		int v;
		scanf("%d%d",&v,&up[i]);
		dijkstra(i,v);
		//for(int j=1;j<=n;++j){
			//printf("i:%d j:%d dis:%lld\n",i,j,dis[i][j]);
		//}
	} 
	sort(d+1,d+c+1);
	c=unique(d+1,d+c+1)-(d+1);
	ll l=1,r=c;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(ok(d[mid])){
			r=mid-1;
		} 
		else{
			l=mid+1;
		}
	}
	printf("%lld\n",d[l]);
	return 0;
}