二分答案+最大流。
对答案建图，若长度≤答案，连边即可。（先要预处理点对间的最短路）
当然得拆点，（否则，就此题而言，就会出现流量x-y不走x-y的最短路边的情况，而是走了一条路径 ，答案约束的仅仅是路径上的边长的最大值，而非总和）
流量：S - 某点入点 - 某点出点 - T
另外，由于此题卡实现，考虑二分边权集合，就酱
吐槽 第一次建图时“因为一头牛经过边(x,y,c)用时为c，所以对于时限t来说，这条边的容量为t/c。 ”woc我在想什么。。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e2+7;
const int L=2e6+7;
const int inf=0x3f3f3f3f3f3f3f3f;
int S=N-1,T=N-2;
int head[N],to[L],upp[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;
inline void add_edge(int x,int y,int u1,int u2=0) {
to[++cnt]=y,upp[cnt]=u1,last[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,upp[cnt]=u2,last[cnt]=head[y],head[y]=cnt;
}
inline bool bfs() {
memset(lev,0,sizeof lev);
lev[S]=1;
que[hd=0,tl=1]=S;
while(hd<tl) {
int x=que[++hd];
for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]])
lev[to[i]]=lev[x]+1, que[++tl]=to[i];
}
return lev[T]!=0;
}
int dfs(int x,int tf) {
if(x==T) return tf;
int tot=0,tmp;
for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
tmp=dfs(to[i],min(tf-tot,upp[i]));
if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;
if(tot==tf) break;
}
if(!tot) lev[x]=-1;
return tot;
}
int n,m,sum;
int s[210],p[210],dis[210][210];
struct edge {
int x,y,w;
bool operator<(const edge&d) const {
return w<d.w;
}
} c[40010];
int d[40010];
inline bool check(int lmt) {
cnt=1;
memset(head,0,sizeof head);
for(int i=1; i<=n; ++i) {
add_edge(S,i,s[i]);
add_edge(n+i,T,p[i]);
}
for(int i=1; c[i].w<=lmt && i<=m; ++i) {
add_edge(c[i].x,n+c[i].y,inf);
add_edge(c[i].y,n+c[i].x,inf);
}
int tot=0;
while(bfs()) tot+=dfs(S,inf);
return tot>=sum;
}
signed main() {
scanf("%lld%lld",&n,&m);
memset(dis,0x3f,sizeof dis);
for(int i=1; i<=n; ++i) {
scanf("%lld%lld",s+i,p+i);
dis[i][i]=0;
sum+=s[i];
}
for(int i=1,x,y,w; i<=m; ++i) {
scanf("%lld%lld%lld",&x,&y,&w);
if(dis[x][y]>w) {
dis[x][y]=w;
dis[y][x]=w;
}
}
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]);
}
}
}
m=0;
for(int i=1; i<=n; ++i) {
for(int j=i; j<=n; ++j) {
if(dis[i][j]<inf) c[++m]=(edge){i,j,dis[i][j]};
}
}
sort(c+1,c+m+1);
int l=1,r=0,mid,ans=-1;
for(int i=1; i<=m; ++i) {
if(c[i].w!=c[i-1].w) d[++r]=c[i].w;
}
while(l<=r) {
mid=(l+r)>>1;
if(check(d[mid])) ans=d[mid],r=mid-1;
else l=mid+1;
}
printf("%lldn",ans);
return 0;
} 内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
