2024-04-03
上午去杜甫草堂了
中午吃火锅了
下午打球了
晚上来写题了
(就写了一个……)
Exploration plan
发现答案是有上界的
并且是最小化最大值
直接想到二分
Floyd 预处理 两点之间的距离
二分一个 limit
点拆成左右两个
每次距离不超过 limit 的点对之间连容量为 Inf 的边表示可以转移棋子
源点向每个左部点连容量为初始棋子数的边,表示最多能转移这么多
每个右部点向汇点连容量为 1 的边,因为移动更多的棋子到这里一定不会更优秀
注意:
- 可能有重边,保留最小值
- 也可以向自己转移棋子,所以 Floyd 自己到自己的距离设置为 0
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int V=800,E=30000;
const int N=V*2+100,M=2*(2*V+V*V+100);
const int Inf=1e8;
int n,m;
int key;
int num,cnt[V],pos[V];
int dis[V][V];
int hd[N],edg[M],nxt[M],cap[M],idx;
int cur[N],dep[N];
int s,t;
void adde(int u,int v,int w) {
edg[idx]=v,cap[idx]=w,nxt[idx]=hd[u],hd[u]=idx++;
edg[idx]=u,cap[idx]=0,nxt[idx]=hd[v],hd[v]=idx++;
}
bool bfs() {
memset(dep,-1,sizeof(dep));
queue<int> q;
dep[s]=0,cur[s]=hd[s];
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=hd[u];~i;i=nxt[i]) {
int v=edg[i];
if(dep[v]==-1&&cap[i]) {
dep[v]=dep[u]+1;
cur[v]=hd[v];
if(v==t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int lim) {
if(u==t) return lim;
int flw=0;
for(int i=cur[u];~i&&flw<lim;i=nxt[i]) {
cur[u]=i;
int v=edg[i];
if(dep[v]==dep[u]+1&&cap[i]) {
int tmp=dfs(v,min(cap[i],lim-flw));
if(!tmp) dep[v]=-1;
cap[i]-=tmp,cap[i^1]+=tmp;
flw+=tmp;
}
}
return flw;
}
int dinic() {
int res=0,flw;
while(bfs()) while(flw=dfs(s,Inf)) res+=flw;
return res;
}
void build(int lim) {
idx=2;
memset(hd,-1,sizeof(hd));
s=0,t=2*n+1;
for(int u=1;u<=n;u++) {
adde(s,u,cnt[u]);
for(int v=1;v<=n;v++)
if(dis[u][v]<=lim) adde(u,v+n,Inf);
}
for(int v=1;v<=n;v++) adde(v+n,t,1);
}
bool check(int lim) {
build(lim);
return dinic()>=key;
}
signed main() {
scanf("%lld%lld%lld%lld",&n,&m,&num,&key);
for(int i=1;i<=num;i++) {
scanf("%lld",&pos[i]);
cnt[pos[i]]++;
}
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++) {
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
dis[u][v]=dis[v][u]=min(dis[u][v],w);
}
for(int i=1;i<=n;i++) dis[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++) printf("%d ",dis[i][j]);
// puts("");
// }
if(!check(1731311)) {
puts("-1");
return 0;
}
int lft=0,rgh=2000000,ans=-1;
while(lft<=rgh) {
int mid=lft+rgh>>1;
if(check(mid)) ans=mid,rgh=mid-1;
else lft=mid+1;
}
printf("%lld\n",ans);
return 0;
}
标签:03,04,idx,int,cur,2024,dep,hd,edg
From: https://www.cnblogs.com/Orange-Star/p/18113566