Solution
两道比较裸的题。。。
复习一下最大流和费用流的模板。
Code[bzoj 2768][JLOI 2010] 冠军调查
#include#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}#define MN 505#define T 500#define S 0#define ME 200000#define inf 0x3f3f3f3fstruct edge{int to,w,nex;}e[ME];int hr[MN],cur[MN],en=1;inline void ins(int f,int t,int w){ e[++en]=(edge){t,w,hr[f]};hr[f]=en; e[++en]=(edge){f,0,hr[t]};hr[t]=en;}int d[MN],q[MN],top;bool bfs(){ memset(d,0,sizeof d); register int i,j; for(d[q[i=top=1]=S]=1;i<=top;++i) for(j=hr[q[i]];j;j=e[j].nex) if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[T];}int dfs(int x,int f){ if(x==T) return f; int used=0,w; for(int i=cur[x];i;i=e[i].nex) { cur[x]=i; if(d[e[i].to]==d[x]+1&&e[i].w) { w=dfs(e[i].to,min(e[i].w,f-used)); used+=w;e[i].w-=w;e[i^1].w+=w; if(f==used) return used; } } return d[x]=-1,used;}int ans=0;void solve(){ while(bfs()) { memcpy(cur,hr,sizeof cur); ans+=dfs(S,inf); }}int main(){ register int i,x,y,n=read(),m=read(); for(i=1;i<=n;++i) read()?ins(S,i,1):ins(i,T,1); while(m--) x=read(),y=read(),ins(x,y,1),ins(y,x,1); solve();return 0*printf("%d\n",ans);}
Code[bzoj 1877][SDOI 2009]晨跑
#include#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}#define MN 505#define ME 41000#define inf 0x3f3f3f3fstruct edge{int to,w,c,nex;}e[ME];int hr[MN],en=1,S,T;inline void ins(int f,int t,int w,int c){ e[++en]=(edge){t,w,c,hr[f]}; hr[f]=en; e[++en]=(edge){f,0,-c,hr[t]};hr[t]=en;}int d[MN],q[ME<<2],l,r;bool inq[MN],vis[MN];bool spfa(){ memset(d,0x3f,sizeof d); d[q[l=r=ME]=T]=0;inq[T]=true; register int i; while(l<=r) { int u=q[l++];inq[u]=false; for(i=hr[u];i;i=e[i].nex) if(e[i^1].w&&d[e[i].to]>d[u]-e[i].c) { d[e[i].to]=d[u]-e[i].c; if(inq[e[i].to]) continue; inq[e[i].to]=true; d[e[i].to]<=d[q[l]]?q[--l]=e[i].to:q[++r]=e[i].to; } } return d[S]!=inf;}ll mincost=0,maxflow=0;int dfs(int x,int f){ vis[x]=true; if(x==T) return f; int used=0,w; for(int i=hr[x];i;i=e[i].nex) if(e[i].w&&d[e[i].to]+e[i].c==d[x]&&!vis[e[i].to]) { w=dfs(e[i].to,min(e[i].w,f-used)); used+=w;e[i].w-=w;e[i^1].w+=w; mincost+=1ll*w*e[i].c; if(used==f) return f; } return used;}void solve(){ while(spfa()) { do { memset(vis,0,sizeof vis); maxflow+=dfs(S,inf); }while(vis[T]); }}int main(){ register int x,y,c,N=read(),M=read(),i; for(i=1;i<=N;++i) ins(i,i+N,1,0); while(M--) x=read(),y=read(),c=read(),ins(x+N,y,1,c); S=1+N;T=N; solve();return 0*printf("%lld %lld\n",maxflow,mincost);}
Blog来自PaperCloud，未经允许，请勿转载，TKS！