蚯蚓的游戏问题 wikioi 1033

典型的网络流问题。把每一堆食物，分解成两个点（这里为什么要拆成两个点，我一直没想明白，后来才发现，题目中说每个结点只能经过一次，而假如每堆食物当成一个点，就无法保证改点只经过一次。要是不拆分，则此题只能拿50分），a，b。由a到b建立一个容量为1，cost为该堆食物量的负值的边（因为要求最大费用，所以用负值来代替，最后结果再取负即可）。在建立0结点和1结点。0结点向1结点建立一个容量为k，cost为0的边。1结点向第一行的所有a结点建立容量为1，cost为0的边。再建立超级汇结点，最后一行的b结点向超级汇结点建立容量为1，cost为0的边，之后求最大流最小费用流（最大流最小费用模板代码）。

我的AC代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define INT_MAX 0x07777777
struct Edge {
    int from,to,cap,flow,cost;
};
int n,m,k,sz,result;
vector<int> G[3100];
vector<Edge> edges;
vector<int> ss,tempss;
int inq[3100],d[3100],a[3100],p[3100];
void AddEdge(int from, int to, int cap,int flow,int cost){
    edges.push_back(Edge{from,to,cap,flow,cost});
    edges.push_back(Edge{to,from,0,0,0-cost});
    int count = edges.size();
    G[from].push_back(count-2);
    G[to].push_back(count-1);
}
void init(){
    scanf("%d %d %d",&n,&m,&k);
    memset(inq, 0, sizeof(inq));
    memset(d, 0, sizeof(d));
    result = 0;
    sz = 2;
    for(int i = 0; i < 3100; i++) G[i].clear();
    ss.clear();
    edges.clear();
    AddEdge(0, 1, k, 0, 0);
    ss.push_back(1);
    for(int i = 0; i < n; i++){
        int temp;
        tempss.clear();
        for(int j = 0; j < ss.size(); j++){
            tempss.push_back(ss[j]);
        }
        ss.clear();
        for(int j = 0; j < m+i; j++){
            scanf("%d",&temp);
            if (i==0) {
                AddEdge(tempss[0], sz, 1, 0, 0);
                sz++;
                AddEdge(sz-1, sz, 1, 0, -temp);
                ss.push_back(sz);
                sz++;

            } else {
                int to = sz;
                if(j>0) {
                    AddEdge(tempss[j-1], to, 1, 0, 0);
                }
                if(j<m+i-1) {
                    AddEdge(tempss[j], to, 1, 0, 0);
                }
                sz++;
                AddEdge(to, sz, 1, 0, -temp);
                ss.push_back(sz);
                sz++;
            }
        }
    }
    for(int i = 0; i < m+n-1; i++){
        
        AddEdge(ss[i], sz, 1, 0, 0);
    }
    sz++;
}
bool solve(){
    queue<int> q;
    for(int i = 0; i < 3100; i++) d[i] = INT_MAX;
    memset(inq, 0, sizeof(inq));
    a[0] = INT_MAX;
    d[0] = 0;
    q.push(0);
    inq[0] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for(int i = 0; i < G[u].size(); i++){
            Edge& edge = edges[G[u][i]];
            if (d[edge.to] > d[u]+edge.cost && edge.cap > edge.flow) {
                d[edge.to] = d[u]+edge.cost;
                if (!inq[edge.to]) {
                    q.push(edge.to);
                    inq[edge.to] = 1;
                }
                a[edge.to] = (a[u] < edge.cap-edge.flow ? a[u] : edge.cap-edge.flow);
                p[edge.to] = G[u][i];
            }
        }
    }
    if (d[sz-1]==INT_MAX) {
        return false;
    }
    int u = sz-1;
    while (u) {
        edges[p[u]].flow += a[sz-1];
        edges[p[u]^1].flow -= a[sz-1];
        u = edges[p[u]].from;
    }
    result -= d[sz-1];
    return true;
}
int main(int argc, const char * argv[])
{
    init();
    while(solve());
    printf("%d\n",result);
}