noj2112拯救活动室的男女比例（最大费用最大流）

拯救活动室的男女比例

只要跟题目所说的一样能达到就连边即可，注意一个点要拆成两个点，为了让费用只能加一次，拆成两个点后连两条边，一条容量为1，费用为aij，一条容量为k，费用为0，由于是最大费用最大流，所以如果会经过这个店，一定会先流容量为1的边

代码：

#include
#include
#include
#include
#include
#include
using namespace std;
#define N 1350
#define INF 999999999
struct Edge
{int u,v,next,cap,cost;
} edge[N*N];
int cnt,head[N];
int vis[N],pp[N];
long long d[N];
void init()
{cnt=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cap=cap;edge[cnt].cost=cost;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cap=0;edge[cnt].cost=-cost;edge[cnt].next=head[v];head[v]=cnt++;
}
int spfa(int s,int t,int n)
{queueq;memset(vis,0,sizeof(vis));memset(pp,-1,sizeof(pp));///pp[i]表示最短路径上以i为终点的边的编号for(int i=0; i<=n; i++)d[i]=-INF;d[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u]; i!=-1; i=edge[i].next){int v=edge[i].v;if(edge[i].cap>0&&d[v]}
long long MCMF(int s,int t,int n)
{long long mincost=0;int minflow;///最大费用，路径中最小流量，总流量while(spfa(s,t,n))///找当前的最长路{minflow=INF+1;for(int i=pp[t]; i!=-1; i=pp[edge[i].u])minflow=min(minflow,edge[i].cap);///从路径中找最小的流量for(int i=pp[t]; i!=-1; i=pp[edge[i].u]){edge[i].cap-=minflow;///当前边减去最小流量edge[i^1].cap+=minflow;///反向边加上最小流量}mincost+=d[t]*minflow;///最小费用等于路径和*每条路径的流量（经过多少次）}return mincost;
}
int main()
{int n,m,k,v,T,tot=1;scanf("%d",&T);while(T--){init();scanf("%d %d",&m,&k);int s=0,n=2*m*m+1;addedge(s,1,k,0);for(int i=1; i<=m; i++){for(int j=1; j<=i; j++){scanf("%d",&v);addedge((i-1)*m+j,m*m+(i-1)*m+j,1,v);addedge((i-1)*m+j,m*m+(i-1)*m+j,k,0);if(i!=m) addedge(m*m+(i-1)*m+j,i*m+j,k,0);if(j!=i) addedge(m*m+(i-1)*m+j,(i-1)*m+j+1,k,0);}}addedge(2*m*m,n,k,0);printf("%I64d\n",MCMF(s,n,n));}return 0;
}