题意就是求一个最大流最小费用与最大费用，模板
思路：
源点到每个点建流为1，距离为0的点每个点到汇点建流为1，距离为0的点中间的点按照所给出的距离图来建立流为1的边求最小值加正向距离的边，求最大值加距离的相反数。
每次跑一次spfa找出一条S->T的最短距离，将答案加入并且更新流。
当spfa到S不能到达T时输出答案。
记录一下模板：
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<stack> #include<vector> #include<map> #include<queue> #define myself i,l,r #define lson i<<1 #define rson i<<1|1 #define Lson i<<1,l,mid #define Rson i<<1|1,mid+1,r #define half (l+r)/2 #define inff 0x3f3f3f3f #define lowbit(x) x&(-x) #define PI 3.14159265358979323846 #define min4(a,b,c,d) min(min(a,b),min(c,d)) #define min3(x,y,z) min(min(x,y),min(y,z)) #define pii make_pair #define pr pair<int,int> const int dir[4][2]={0,1,0,-1,1,0,-1,0}; typedef long long ll; const ll inFF=9223372036854775807; typedef unsigned long long ull; using namespace std; //最大流费用流 const int maxn=210; const int maxm=3e4+10; int pre[210],flow[210],dis[210],vis[210]; int head[210],sign; int mp[105][105]; struct node { int to,p,f,d; }edge[maxm]; int n,st,ed,mincost; void init() { sign=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int f,int d) { edge[sign]=node{v,head[u],f,d}; head[u]=sign++; } void add_edge(int u,int v,int f,int d)//加双向边 { add(u,v,f,d); add(v,u,0,-d); } bool spfa()///跑sfpa顺便更新流 { for(int i=0;i<=2*n+1;i++) { vis[i]=0; pre[i]=-1; flow[i]=dis[i]=inff; } vis[st]=1,dis[st]=0; queue<int> q; q.push(st); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];~i;i=edge[i].p) { int v=edge[i].to,f=edge[i].f,d=edge[i].d; if(dis[v]>dis[u]+d&&f>0) { dis[v]=dis[u]+d; flow[v]=min(flow[u],f); pre[v]=i;///pre[v]记录 u->v的这条边的编号 if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[ed]!=inff; } void MCMF() { mincost=0; while(spfa()) { int f=flow[ed]; /// maxflow+=f; 这里求最大流 mincost+=f*dis[ed];///这里求最小费用 /// pre[v]=i 记录 u->v的边编号为i 那么i^1这条边记录v->u,edge[i^1].to=u; for(int i=pre[ed];~i;i=pre[edge[i^1].to])///更新流 { edge[i].f-=f; edge[i^1].f+=f; } } } int main() { cin>>n; st=0,ed=2*n+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); init(); for(int i=1;i<=n;i++) { add_edge(0,i,1,0),add_edge(i+n,ed,1,0); for(int j=1;j<=n;j++) add_edge(i,j+n,1,mp[i][j]); } MCMF(); cout<<mincost<<endl; init(); for(int i=1;i<=n;i++) { add_edge(0,i,1,0),add_edge(i+n,ed,1,0); for(int j=1;j<=n;j++) add_edge(i,j+n,1,-mp[i][j]); } MCMF(); cout<<-mincost<<endl; return 0; }
