?id=2391
写的挫的最大流会超时~~~
题目描述： Jack 农场主的奶牛实在是太讨厌被淋湿了。决定在农场设置降雨警报，这样在快要下 雨的时候可以让奶牛们都知道。他们设置设计了一个下雨撤退计划，这样在下雨之前每头奶牛都 能躲到避雨点。然而，天气预报并不总是准确的。为了使得错误的天气预报影响尽可能小，他们 希望尽可能晚地拉响警报，只要保证留有足够的时间让所有的奶牛都能回到避雨点就可以了。 农场有F 块草地，1≤F≤200，，奶牛们在草地上吃草。这些草地之间有P 条路相连，1≤P≤ 1500，这些路足够宽，再多的奶牛也能同时在路上行走。 有些草地上有避雨点，奶牛们可以在此避雨。避雨点的容量是有限的，所以一个避雨点不可 能容纳下所有的奶牛。草地与路相比很小，奶牛们通过时不需要花费时间。 计算警报至少需要提前多少时间拉响，以保证所有的奶牛都能到达一个避雨点。
输入描述： 测试数据的格式如下： (1) 第1 行为两个整数，F 和P。 (2) 第2～F+1 行，每行为两个整数，描述了一块草地，前一个整数（范围为0～1000），表 示在该草地吃草的奶牛数量；后一个整数（范围为0～1000）该草地的避雨点能容纳的奶牛数量。 (3) 第F+2～F+P+1 行，每行有3 个整数，描述了一条路，第1 个和第2 个整数（范围为1～ F）为这条路连接的两块草地序号，第3 个整数（范围为0～1000,000,000），表示任何一头奶牛 通过这条路是需要花费的时间。
输出描述： 输出所有奶牛回到避雨点所需的最少时间，如果不能保证所有的奶牛都回到一个避雨点，则 输出”-1”。
**每个点拆成两个点，点i拆成i和i+n,i和i+n连边为无穷。则源点到i连边的容量为初始的奶牛数，i+n到汇点的连边为避雨点所能容纳的奶牛数，如果点i,j之间右边，则i到j+n的连边容量为无穷。 因为要求时间最少，所以是路径最短，先用floyd求得任意两点之间的最短路，牛转移的方法是同时的，不是一堆一堆转移的，所以二分枚举最小的边使得满流，就是所要求的答案**
新技能get 2060K 329MS C++ 3800B
maxn= maxm = INF=0x3f3f3f3f;;int n,s,t,N;//输入的顶点数，源点，汇点，建图后的总顶点数（判断dis[s]<N)struct node{int to,cap,next,pre;//pre是指互为反向弧}edges[maxm];int head[maxn],tot,que[maxn],d[maxn],gap[maxn],cur[maxn],rpath[maxn];//邻接表，边数，队列，距离标号，间隙优化，当前弧，可增广路上的弧编号void init(){tot=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int c){edges[tot].to=v;edges[tot].cap=c;edges[tot].next=head[u];head[u] = tot ++;edges[tot-1].pre=tot;edges[tot].pre = tot-1;edges[tot].cap = 0;edges[tot].to = u;edges[tot].next = head[v];head[v] = tot ++;}void re_Bfs(){memset(gap,0,sizeof(gap));memset(d,-1,sizeof(d));int i,front=0,rear=0;que[rear ++] = t;gap[0] = 1;d[t] = 0;while(front != rear){int u = que[front ++];for(i = head[u];i != -1;i = edges[i].next){if(edges[edges[i].pre].cap == 0 || d[edges[i].to]!=-1)continue;d[edges[i].to] = d[u] + 1;gap[d[edges[i].to]] ++;que[rear ++] = edges[i].to;}}}int ISAP(){memset(gap,0,sizeof(gap));memset(d,0,sizeof(d));memcpy(cur,head,sizeof(head));int i,u=s,maxflow = 0;while(d[s] < N){if(u == t){int curflow = INF;for(i = s;i != t;i = edges[cur[i]].to)curflow = min(curflow,edges[cur[i]].cap);for(i = s;i != t;i = edges[cur[i]].to){edges[cur[i]].cap -= curflow;edges[edges[cur[i]].pre].cap += curflow;}maxflow += curflow;u = s;}for(i = cur[u];i != -1;i = edges[i].next)if(edges[i].cap > 0 && d[edges[i].to] + 1 == d[u])break;if(i != -1){cur[u] = i;rpath[edges[i].to] = edges[i].pre;u = edges[i].to;}else{if((– gap[d[u]]) == 0) break;cur[u] = head[u];int Min = N;for(i = cur[u];i != -1;i = edges[i].next)if(edges[i].cap > 0)Min = min(Min,d[edges[i].to]);gap[d[u]=Min+1] ++;if(u != s) u = edges[rpath[u]].to;}}return maxflow;}int cow[maxn],cury[maxn],sum,m;ll dist[maxn][maxn];void Build_Graph(ll mid){init();for(int i=1;i<=n;++i){addedge(s,i,cow[i]);addedge(i,i+n,INF);addedge(i+n,t,cury[i]);for(int j=1;j<=n;++j){if(dist[i][j]<=mid)addedge(i,j+n,INF);}}}void floyd(){for(int k=1;k<=n;++k){for(int i=1;i<=n;++i){for(int j=1;j<=n;++j)if(dist[i][k]<inf&&dist[k][j]<inf)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}}void solve(){ll l=1,r=inf-1,mid,ans=-1;s=0,t=n+n+1,N=n+n+2;while(l<r){mid=(l+r)>>1;Build_Graph(mid);int tmp=ISAP();if(tmp==sum) ans=mid;if(tmp>=sum) r=mid;else l=mid+1;}printf(“%I64d\n”,ans);}void Init(){sum=0;int u,v;ll w;scanf(“%d%d”,&n,&m);for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dist[i][j]=inf;for(int i=1;i<=n;++i){scanf(“%d%d”,&cow[i],&cury[i]);sum+=cow[i];}while(m–){scanf(“%d%d%I64d”,&u,&v,&w);dist[u][v]=dist[v][u]=min(w,dist[u][v]);}floyd();}int main(){Init();solve();return 0;}
还深深埋在心底，要除去，怕是不能活命。
