裸費用流 老套路 拆點限制流量 然后直接跑費用流 注意要在源點與第一行直接再加一個點以便選擇最優的解.
#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int max_n=50;const int max_m=50;const int max_N=(max_n+2*max_m-1)*max_n+4;const int max_M=max_n*max_m*4;const int max_e=max_M*2;const int inf=1e9;int n,m,k,food,x1,x2,y1,y2,cnt,maxflow,maxcost,N;int next[max_e],point[max_N],v[max_e],remain[max_e],c[max_e],tot;int last[max_N],dis[max_N],vis[max_N];queue <int> q;inline void addedge(int x,int y,int cap,int z){ ++tot; next[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; c[tot]=z; ++tot; next[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; c[tot]=-z;}inline int addflow(int s,int t){ int ans=inf,now=t; while (now!=s){ ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s){ remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans;}inline bool bfs(int s,int t){ memset(dis,128,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=true; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()){ int now=q.front(); q.pop(); vis[now]=false; for (int i=point[now];i!=-1;i=next[i]) if (dis[v[i]]<dis[now]+c[i]&&remain[i]){ dis[v[i]]=dis[now]+c[i]; last[v[i]]=i; if (!vis[v[i]]){ vis[v[i]]=true; q.push(v[i]); } } } if (dis[t]<0) return false; int flow=addflow(s,t); maxflow+=flow; maxcost+=flow*dis[t]; return true;}inline void major(int s,int t){ maxflow=0; maxcost=0; while (bfs(s,t));}int main(){ tot=-1; memset(point,-1,sizeof(point)); memset(next,-1,sizeof(next)); scanf("%d%d%d",&n,&m,&k); N=(n+2*m-1)*n+4; for (int i=1;i<=n;++i) for (int j=1;j<=m+i-1;++j){ scanf("%d",&food); ++cnt; x1=cnt*2+1; x2=cnt*2+2; addedge(x1,x2,1,food); if (i==1) addedge(2,x1,inf,0); if (i!=n){ y1=(cnt+m+i-1)*2+1; y2=(cnt+m+i)*2+1; addedge(x2,y1,inf,0); addedge(x2,y2,inf,0); } else addedge(x2,N-1,inf,0); } addedge(1,2,k,0); addedge(N-1,N,k,0); major(1,N);新聞熱點
疑難解答
