[费用流]hdoj 5045

读题的时候漏掉了“题目是按照顺序出现的”，导致网络赛中这道题没有做掉，用了一种错误的构图方式一直t到了最后

其实按照题目中的办法，做m/n次费用流就可以了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int inf=99999999;
const int nMax=1030;
const int mMax=30005;
struct{
    int v, cap,  next, re;
    double cost;
}edge[40005];
int nnn,mmm;
double ans;
int k,edgeHead[nMax];
int que[nMax],pre[nMax];
double dis[nMax];
bool vis[nMax];
void addEdge(int u,int v,int ca,double co){///始点  终点  流量  费用
    //cout<<u<<"add"<<v<<" ca="<<ca<<" cost"<<co<<endl;
    edge[k].v=v;
    edge[k].cap=ca;
    edge[k].cost=co;
    edge[k].next=edgeHead[u];
    edge[k].re=k + 1;
    edgeHead[u]=k ++;
    edge[k].v=u;
    edge[k].cap=0;
    edge[k].cost=-co;
    edge[k].next=edgeHead[v];
    edge[k].re=k - 1;
    edgeHead[v]=k ++;
}
bool spfa(){
    int i, head = 0, tail = 1;    //  长注释的地方就是从最小费用改到最大费用时需要变动的地方
    for(i = 0; i <= nnn; i ++){
        dis[i] = -1;////////////
        vis[i] = false;
    }
    dis[0] = 0;
    que[0] = 0;
    vis[0] = true;
    while(head != tail){
        int u = que[head];
        for(i = edgeHead[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap && dis[v] <dis[u] + edge[i].cost){////////
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                }
            }
        }
        vis[u] = false;
        head++;
        if(head ==nMax) head = 0;
    }
    if(dis[nnn] ==-1) return false;///////////
    return true;
}
//int mark;
int n,m;
void end(){
    int u, p;
    for(u = nnn; u != 0; u = edge[edge[p].re].v){
        p = pre[u];
        edge[p].cap -= 1;
        edge[edge[p].re].cap += 1;
        ans += edge[p].cost;
    }
}
void initspfa(){
    k=1;
    memset(edgeHead,0,sizeof(edgeHead));
    memset(vis,0,sizeof(vis));
}
double mtx[15][1005];
int main(){
    int cnn=0,t,i,j,loc;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%lf",&mtx[i][j]);
            }
        }
        loc=1;
        ans=0;
        while(loc<=m){
            initspfa();
            for(i=1;i<=n;i++){
                addEdge(0,i,1,0);
                addEdge(i+n,2*n+1,1,0);
            }
            for(i=loc;i<loc+n&&i<=m;i++){
                for(j=1;j<=n;j++){
                    addEdge(j,i-loc+1+n,1,mtx[j][i]);
                }
            }nnn=2*n+1;
            while(spfa())end();
            loc+=n;
        }
        printf("Case #%d: %.5lf\n",++cnn,ans);
    }
    return 0;
}