题目地址:HDU 1839
我去。。原来这题这么简单。。。网络流中这种二分建图的方式做了一大堆了。。这种题还能难倒我吗。。。白天一直没怎么看懂题,对题意懵懵懂懂的。。。晚上好好看了看题,这不就是网络流中练的最多的那种二分建图模型吗。。。。只是把网络流算法改成最短路就行了。。但是两个地方手残了没能在实验室当场A掉。。sad。。。
这题就是二分最小容量,对满足容量的加边,对时间求最短路。如果最短时间比规定时间少的话就可以继续增加容量,直到不能增加为止。
代码如下:
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; int head[11000], vis[11000], d[11000], cnt, n; struct node1 { int u, v, w, cost; }bian[50002]; struct node { int u, v, w, next, cost; }edge[1000000]; void add(int u, int v, int w, int cost) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; } int spfa() { memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); d[1]=0; deque<int>q; q.push_back(1); while(!q.empty()) { int u=q.front(); q.pop_front(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost) { d[v]=d[u]+edge[i].cost; if(!vis[v]) { vis[v]=1; if(!q.empty()&&d[v]<d[q.front()]) { q.push_front(v); } else { q.push_back(v); } } } } } } int main() { int t, i, m, time, max1; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&time); max1=-1; for(i=0;i<m;i++) { scanf("%d%d%d%d",&bian[i].u,&bian[i].v,&bian[i].w,&bian[i].cost); if(max1<bian[i].w) max1=bian[i].w; } __int64 low=0, high=max1, mid, ans=-1; while(low<=high) { mid=(low+high)/2; memset(head,-1,sizeof(head)); cnt=0; for(i=0;i<m;i++) { if(bian[i].w>=mid) { add(bian[i].u,bian[i].v,bian[i].w,bian[i].cost); add(bian[i].v,bian[i].u,bian[i].w,bian[i].cost); } } spfa(); if(d[n]<=time) { low=mid+1; ans=mid; } else { high=mid-1; } } printf("%d\n",ans); } return 0; }
HDU 1839 Delay Constrained Maximum Capacity Path(二分+最短路),布布扣,bubuko.com
HDU 1839 Delay Constrained Maximum Capacity Path(二分+最短路)
原文:http://blog.csdn.net/scf0920/article/details/38342865