大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
联系:http://poj.org/problem?id=2391
题意:有f个草场,每一个草场当前有一定数目的牛在吃草,下雨时它能够让一定数量的牛在这里避雨,f个草场间有m条路连接,每头牛通过一条路从一点到还有一点有一定的时间花费,如今要下雨了,农场主发出警报牛就会马上去避雨。
如今告诉每一个草场的情况。以及m条边的信息。农场主至少须要提前多久发出警报才干保证全部牛都能避雨?假设不是全部牛都能成功避雨输出-1。
思路:这道题须要拆点,是看到魏神的博客才知道的。我们把原图拆成一个二分图,避免突破最大距离限制的情况,每一个点变成两个点,即i变为i‘和i’‘,建立一个源点连接每一个i’,容量为初始每一个草场牛的数目。建立一个汇点,全部的i‘’指向汇点,容量为每一个草场能容纳的牛的数目。假设两个点i和j连接。则在i’和j‘’以及j‘和i’‘之间建一条路径。容量为INF,能够走无限多的牛。然后这道题就和之前做的一道POJ2112一样了,POJ2112不用拆点,由于它本身就是一个二分图。
接下来就是Floyd处理出随意两点间最短路径。然后二分答案。
可是这道题还没有完,我套之前的Dinic模板,TLE了。这道题最大可能的边数比POJ2112大,而Case时限一样,我手写队列。还是TLE,我再把vis数组去掉用dist取代vis功能,还是TLE,我在网上搜AC的Dinic代码,看到一个和我的差点儿相同。粘贴交了一发。TLE,无力吐槽。。。
找到了一个看上去有些修改的代码,依照它修改的地方改我自己的。219MS AC。
我看了一下。我认为基本的优化地方是这样:
1. 我之前的模板,是从源点起找遍每一条增广路进行松弛,优化算法是找到一条增广路松弛、退出,更新最大流值,再找下一条,直到更新值返回0说明已更新到头,避免了多余的搜索。
2. 假设此时的顶点已不存在增广路,将它从当前的层次网络中删除。回溯后不会再搜。
我认为这是两个优化到的地方,这么进行了优化之后效率提升非常明显!
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 200100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct node{ int u,w,next; }edge[100010]; int head[410],dist[410],q[410]; int aa[410],bb[410]; ll e[410][410]; int n,m,cnt,src,sink,f,p; void add_edge(int a,int b,int c){ edge[cnt].u = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } void floyd(){ int i,j,k; for(k=1;k<=f;k++){ for(i=1;i<=f;i++){ if(e[i][k]==LLINF) continue; for(j=1;j<=f;j++){ if(e[i][k]+e[k][j]<e[i][j]&&e[i][k]!=LLINF&&e[k][j]!=LLINF) e[i][j] = e[i][k] + e[k][j]; } } } } void build_graph(ll minm){ int i,j; cnt = 0; memset(head,-1,sizeof(head)); for(i=1;i<=f;i++){ add_edge(src,i,aa[i]); add_edge(i,src,0); add_edge(i+f,sink,bb[i]); add_edge(sink,i+f,0); for(j=1;j<=f;j++){ if(e[i][j]<=minm){ add_edge(i,j+f,INF); add_edge(j+f,i,0); } } } } bool bfs(){ int i,j; memset(dist,-1,sizeof(dist)); int f = 0, t = 1; q[0] = src; dist[src] = 1; while(f<t){ int u = q[f++]; for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].u; if(dist[v]==-1&&edge[i].w){ dist[v] = dist[u] + 1; q[t++] = v; } } } if(dist[sink]!=-1) return true; return false; } int dfs(int u,int delta){ int i,j; int dd; if(u==sink) return delta; for(i=head[u];i!=-1;i=edge[i].next){ if(dist[edge[i].u]==dist[u]+1&&edge[i].w&&(dd = dfs(edge[i].u,min(delta,edge[i].w)))){ edge[i].w -= dd; edge[i^1].w += dd; return dd; } } dist[u] = -1; return 0; } int main(){ int i,j; int ta,tb,tc; int cow; scanf("%d%d",&f,&p); n = 2 * f + 2; src = 0; sink = 2 * f + 1; cow = 0; for(i=1;i<=f;i++){ scanf("%d%d",&aa[i],&bb[i]); cow += aa[i]; } for(i=0;i<=f;i++){ for(j=0;j<=f;j++) e[i][j] = LLINF; e[i][i] = 0; } for(i=0;i<p;i++){ scanf("%d%d%d",&ta,&tb,&tc); if(tc<e[ta][tb]) e[ta][tb] = e[tb][ta] = tc; } floyd(); ll mid,l = 0,r = 0; for(i=1;i<=f;i++){ for(j=1;j<=f;j++){ if(e[i][j]!=LLINF) r = max(e[i][j],r); } } int sum; ll ans = -1; while(l<=r){ mid = (l+r)>>1LL; //cout<<l<<" "<<r<<endl; sum = 0; build_graph(mid); while(bfs()){ while(1){ int ttt = dfs(src,INF); if(!ttt) break; sum += ttt; } } if(sum==cow){ ans = mid; r = mid-1; } else l = mid + 1; } printf("%I64d\n",ans); return 0; }
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117083.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...