基本和上一題一樣，裸費用流 而且更簡單
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<queue>using namespace std;const int N=10000,inf=0x3f3f3f3f;int a[N],p[N],inq[N],d[N],val[60][60],head[N];int n,s,t,m,k,te,sz;struct edge{ int u,v,cost,cap,flow,next;}e[50010];queue<int>q;void add(int u,int v,int cap,int cost){ e[++te].u=u; e[te].v=v; e[te].cap=cap; e[te].cost=cost; e[te].next=head[u]; head[u]=te;}void insert(int u,int v,int cap,int cost){add(u,v,cap,cost),add(v,u,0,-cost);}int spfa(int &flow,int &cost){ memset(inq,0,sizeof(inq)); memset(d,-1,sizeof(d)); a[s]=inf,d[s]=0,inq[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); for (int i=head[u];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow&&d[u]+e[i].cost>d[v]) { d[v]=d[u]+e[i].cost; p[v]=i; a[v]=min(a[u],e[i].cap-e[i].flow); if (!inq[v]) { inq[v]=1; q.push(v); } } } inq[u]=0; q.pop(); } if (d[t]==-1)return false; flow+=a[t]; cost+=a[t]*d[t];// cout<<a[t]<<endl<<d[t]<<endl; for (int u=t;u!=s;u=e[p[u]].u) { e[p[u]].flow+=a[t]; e[p[u]^1].flow-=a[t]; } return true;}int mcmf(int &cost){ int flow=0; cost=0; while(spfa(flow,cost)); return flow;}int kkk(int i,int j){return (i-1)*n+j;}int main(){ te=1; cin>>n>>k; sz=n*n,s=(sz<<1)+1,t=s+1; insert(s,1,k,0); insert(sz<<1,t,k,0); for(int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { scanf("%d",&val[i][j]); insert(kkk(i,j),kkk(i,j)+sz,1,val[i][j]); insert(kkk(i,j),kkk(i,j)+sz,inf,0); if (i<n)insert(kkk(i,j)+sz,kkk(i+1,j),inf,0); if (j<n)insert(kkk(i,j)+sz,kkk(i,j+1),inf,0); } } int cost;// for (int i=2;i<=te;i+=2)// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].cap<<' '<<e[i].cost<<endl; mcmf(cost); cout<<cost;}新聞熱點
疑難解答
