bzoj1570: [JSOI2008]Blue Mary的旅行

本文主要是介绍bzoj1570: [JSOI2008]Blue Mary的旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1570

思路：把每天当作一层，一层包含n个点，每层向下一层在原图中有边相连的点连边，表示一天能走一条边，每天的n点向汇连边

枚举天数，每次加一层，满流即输出答案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=10010,inf=1e9,maxm=1000010;
using namespace std;
int n,m,S=maxn-1,T=maxn-2,cnt,q[maxn+10],head,tail,pre[maxm],now[maxn],son[maxm],val[maxm],tot=1,dis[maxn];
struct Edge{int x,y,z;}E[maxm];
void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
void ins(int a,int b,int c){add(a,b,c),add(b,a,0);}bool bfs(){memset(dis,-1,sizeof(dis));q[tail=1]=S,dis[S]=head=0;while (head!=tail){if (++head>maxn) head=1;int x=q[head];for (int y=now[x];y;y=pre[y]) if (dis[son[y]]==-1&&val[y]){if (++tail>maxn) tail=1;dis[son[y]]=dis[x]+1,q[tail]=son[y];}}return dis[T]>0;
}int find(int x,int low){if (x==T) return low;int y,res=0;for (y=now[x];y;y=pre[y]){if (dis[son[y]]!=dis[x]+1||!val[y]) continue;int tmp=find(son[y],min(low,val[y]));val[y]-=tmp,val[y^1]+=tmp,res+=tmp,low-=tmp;if (!low) break;}if (!y) dis[x]=-1;return res;
}void rebuild(){for (int i=2;i<=tot;i+=2)val[i]+=val[i^1],val[i^1]=0;
}int main(){scanf("%d%d%d",&n,&m,&cnt);for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),E[i]=(Edge){x,y,z};ins(S,1,cnt);for (int i=1;i<=n+cnt;i++){rebuild();for (int j=1;j<=m;j++) ins((i-1)*n+E[j].x,i*n+E[j].y,E[j].z);for (int j=1;j<=n;j++) ins((i-1)*n+j,i*n+j,inf);ins(i*n+n,T,inf);int res=0;while (bfs()) res+=find(S,inf);if (res==cnt) return printf("%d\n",i),0;}return 0;
}

这篇关于bzoj1570: [JSOI2008]Blue Mary的旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---