题目地址：HDU 5045
终于在比赛中用网络流A了一道题。。。刷了那么多网络流，终于用到一次了。。虽然题目很简单，但是还是要纪念一下下。。。
我这题的思路就是求m/n次费用流，每n个算作同一轮，对这同一轮的求最大费用流。建图就很简单了，最简单的二分图模型。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 using namespace std; double mp[20][2000], d[200], cost; const int INF=0x3f3f3f3f; int head[200], source, sink, cnt, flow; int f[200], cur[200], vis[200]; struct node { int u, v, cap, next; double cost; } edge[100000]; void add(int u, int v, int cap, double cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { int i; for(i=0; i<200; i++) d[i]=INF; memset(vis,0,sizeof(vis)); cur[source]=-1; f[source]=INF; d[source]=0; queue q; q.push(source); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost-=f[sink]*d[sink]; for(i=cur[sink]; i!=-1; i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } void mcmf() { cost=flow=0; while(spfa()) ; } int main() { int t, num=0, i, j, k, n, m; double sum; scanf("%d",&t); while(t--) { sum=0; num++; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%lf",&mp[i][j]); } } k=1; sum=0; while(k<=m) { source=0; sink=2*n+1; memset(head,-1,sizeof(head)); cnt=0; for(i=k; i