BZOJ1877: [SDOI2009]晨跑
【传送门：BZOJ1877】
简要题意：
给出n个点，起点为1，终点为n，给出m条边，每条边都有费用
每个点只能走一次，请问最多有多少次机会能从起点到终点，并且求出这几次的最小费用和
题解：
一开始还担心有环，实际上没有
最小费用最大流
我们将每个点（除了源点和汇点）都拆成两个点x,y，并且x,y之间的流量为1，费用为0，这样就保证每个点只走一次，并且不影响费用
然后就直接跑费用流，每找到一条增广路就相当于多一次机会，将每条增广路的最小费用加起来即可
空间和小错误卡了很久
参考代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,d,c,next,other; }a[1100000];int len,last[110000]; void ins(int x,int y,int d,int c) { int k1=++len,k2=++len; a[k1].x=x;a[k1].y=y;a[k1].d=d;a[k1].c=c; a[k1].next=last[x];last[x]=k1; a[k2].x=y;a[k2].y=x;a[k2].d=-d;a[k2].c=0; a[k2].next=last[y];last[y]=k2; a[k1].other=k2; a[k2].other=k1; } int d[110000],pre[110000],pos[110000]; bool v[110000]; int list[110000]; int st,ed; bool spfa() { for(int i=st;i<=ed;i++) d[i]=999999999; d[st]=0; memset(v,false,sizeof(v)); v[st]=true; list[1]=st; int head=1,tail=2; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(a[k].c>0&&d[y]>d[x]+a[k].d) { d[y]=d[x]+a[k].d; pos[y]=x; pre[y]=k; if(v[y]==false) { v[y]=true; list[tail++]=y; } } } head++; v[x]=false; } if(d[ed]==999999999) return false; else return true; } int ans,t; void Flow() { while(spfa()) { t++; ans+=d[ed]; int x; for(x=ed;x!=st;x=pos[x]) { a[pre[x]].c--; a[a[pre[x]].other].c++; } } } int main() { int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y,d; scanf("%d%d%d",&x,&y,&d); if(x==1) ins(x,2*(y-1),d,1); else ins(2*(x-1)+1,2*(y-1),d,1); } for(int i=2;i<n;i++) ins(2*(i-1),2*(i-1)+1,0,1); st=1;ed=2*(n-1); ans=t=0; Flow(); printf("%d %d ",t,ans); return 0; }