题目描述
https://www.luogu.org/problemnew/show/P4553
题解
思路比较显然，把图建出来，一个国家拆成两个点，中间设置上下界，然后跑费用流。
我把源那边的流量也设置了上下界，但是题解没有，为什么我按照题解的建图方法会WA？
代码
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define N 209 #define inf 2e9 using namespace std; queue<int>q; int head[N],dis[N],tot=1,pre[N],fl[N],ans,n,m; bool vis[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct edge{int n,to,l,f;}e[50003]; inline void add(int u,int v,int l,int f){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[tot].f=f; e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;e[tot].f=-f; } inline bool spfa(int s,int t){ memset(dis,0x3f,sizeof(dis)); q.push(s);dis[s]=0;fl[s]=2e9; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(e[i].l&&dis[v]>dis[u]+e[i].f){ dis[v]=dis[u]+e[i].f;pre[v]=i;fl[v]=min(fl[u],e[i].l); if(!vis[v]){vis[v]=1;q.push(v);} } } } return dis[t]!=0x3f3f3f3f; } inline void calc(int s,int t){ int x=t; while(x!=s){ int i=pre[x]; e[i].l-=fl[t];e[i^1].l+=fl[t];x=e[i^1].to; } ans+=dis[t]*fl[t]; } int main(){ n=rd();m=rd(); int s=2*n+3,t=2*n+4,x; for(int i=1;i<=n;++i){ x=rd();add(i,t,x,0);add(s,i+n,x,0); add(0,s,m,0);add(i+n,2*n+1,m,0); } // add(2*n+2,0,m,0); add(s,0,m,0);add(2*n+2,t,m,0); add(2*n+1,2*n+2,m,0); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j){ x=rd();if(x>=0)add(i+n,j,m,x); } while(spfa(s,t))calc(s,t); printf("%d ",ans); return 0; }