在FallDream大佬的耐心指导下弄懂了原始对偶算法，跟SPFA比起来多不了几行，以后费用流就打它了。打几题练练手。
[USACO 2003 February]Farm Tour
题目大意：n个点m条边的无向图，要求找到一条路径从1走到n再走回1，不能走重复的边，求最短距离。（n<=1000,m<=10000）
思路：相当于从1选两条不相交的路径走到n，权和最小，比较裸的费用流，每条边建成费用为该边的长度，流量为1，S到1号点连费用0，流量2，n号点到T连费用0，流量2，复杂度O(费用流(n,m))。
#include<cstdio> #include<cstring> inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 1000 #define MM 20002 #define S MN+1 #define T MN+2 #define INF 0x7FFFFFFF struct edge{int nx,t,w,c;}e[MM*2+5]; int h[MN+5],en=1,q[MN+5],qn,inq[MN+5],d[MN+5],dis,ans,mk[MN+5]; inline void ins(int x,int y,int w,int c) { e[++en]=(edge){h[x],y,w,c};h[x]=en; e[++en]=(edge){h[y],x,0,-c};h[y]=en; } inline int next(int x){return x==MN+4?0:x+1;} inline int prev(int x){return x?x-1:MN+4;} bool spfa() { int i,j,x; memset(d,127,sizeof(d)); for(d[q[qn=1,i=0]=T]=0;i!=qn;inq[x]=0,i=next(i))for(j=h[x=q[i]];j;j=e[j].nx) if(e[j^1].w&&d[x]+e[j^1].c<d[e[j].t]) { d[e[j].t]=d[x]+e[j^1].c; if(!inq[e[j].t])if(d[e[j].t]<=d[q[i]])inq[q[i]=e[j].t]=1,i=prev(i); else inq[q[qn]=e[j].t]=1,qn=next(qn); } for(i=1;i<=T;++i)for(j=h[i];j;j=e[j].nx)e[j].c+=d[e[j].t]-d[i]; return dis+=d[S],d[S]<d[0]; } int dfs(int x,int r) { if(x==T)return ans+=dis*r,r; int u=0,k,i;mk[x]=1; for(i=h[x];i;i=e[i].nx)if(!mk[e[i].t]&&e[i].w&&!e[i].c) { k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return r; } return u; } int main() { int n,m,i,x,y; n=read();m=read(); ins(S,1,2,0);ins(n,T,2,0); while(m--)x=read(),y=read(),i=read(),ins(x,y,1,i),ins(y,x,1,i); while(spfa())do memset(mk,0,sizeof(mk));while(dfs(S,INF)); printf("%d",ans); }
餐巾计划问题/[BZOJ]1221 软件开发
题目大意：n天，每天需要ai条餐巾，可以以f元一条的价格买餐巾，或者花fa元洗一条用过的餐巾，a天后可用，或花fb元洗一条用过的餐巾，b天后可用，求最小花费。（n<=1000）
思路：考虑最小费用流，我们把每天拆成两个点，点i表示第i天干净的餐巾，i'表示第i天用过的餐巾，S到i连费用f，流量INF，表示买新的餐巾，S到i'连费用0，流量ai，表示这天新产生了ai条用过的餐巾，点i'向点(i+1)'连费用0，流量INF，表示把用过的餐巾留着不洗备用，点i'向点i+a连费用fa，流量INF的边，表示用一种方式洗餐巾，b同理。复杂度O(费用流(n,n))。下面贴的程序里的建图略有区别，思路大致相同。
#include<cstdio> #include<cstring> inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MV 2000 #define ME 6000 #define S MV+1 #define T MV+2 #define INF 0x7FFFFFFF struct edge{int nx,t,w,c;}e[ME*2+5]; int h[MV+5],en=1,d[MV+5],q[MV+5],qn,inq[MV+5],mk[MV+5],dis,ans; inline void ins(int x,int y,int w,int c) { e[++en]=(edge){h[x],y,w,c};h[x]=en; e[++en]=(edge){h[y],x,0,-c};h[y]=en; } inline int next(int x){return x==MV+4?0:x+1;} inline int prev(int x){return x?x-1:MV+4;} bool spfa() { int i,j,x; memset(d,127,sizeof(d)); for(d[q[qn=1,i=0]=T]=0;i!=qn;inq[x]=0,i=next(i))for(j=h[x=q[i]];j;j=e[j].nx) if(e[j^1].w&&d[x]+e[j^1].c<d[e[j].t]) { d[e[j].t]=d[x]+e[j^1].c; if(!inq[e[j].t])if(d[e[j].t]<=d[q[i]])inq[q[i]=e[j].t]=1,i=prev(i); else inq[q[qn]=e[j].t]=1,qn=next(qn); } for(i=1;i<=T;++i)for(j=h[i];j;j=e[j].nx)e[j].c+=d[e[j].t]-d[i]; return dis+=d[S],d[S]<d[0]; } int dfs(int x,int r) { if(x==T)return ans+=dis*r,r; int i,k,u=0;mk[x]=1; for(i=h[x];i;i=e[i].nx)if(e[i].w&&!e[i].c&&!mk[e[i].t]) { k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return u; } return u; } int main() { int n,f,ta,fa,tb,fb,x,i; n=read();f=read();ta=read();fa=read();tb=read();fb=read(); for(i=1;i<=n;++i) { ins(S,i,INF,0);ins(i,T,x=read(),f);ins(S,i+n,x,0); if(i<n)ins(i+n,i+n+1,INF,0); if(i-ta>0)ins(i+n-ta,i,x,fa-f); if(i-tb>0)ins(i+n-tb,i,x,fb-f); } while(spfa())do memset(mk,0,sizeof(mk));while(dfs(S,INF)); printf("%d",ans); }