[codevs 1913] 数字梯形问题
题解：
本题就是加强版的 [codevs 1033] 蚯蚓的游戏问题。
分别针对三个规则建图、运行最小费用最大流。
规则1：从梯形的顶至底的m条路径互不相交。
分析：因为要互不相交，所以每个点只能走一次，因此要拆点（X->Xi,Xj），容量为1费用为数字相反数，从源点向顶层每个Xi连容量为1，费用为0的边。从底层每个Xj向汇点连一条同样的边。再在相邻边之间连同样的边。最后求解最小费用最大流，取费用相反数就是结果。
规则2：从梯形的顶至底的m条路径仅在数字结点处相交。
分析：仅在数字节点处相交，即一个数字可以经过多次，那么可以放宽Xi和Xj之间容量的限制（由1修改为INF或者m），但注意顶层必须从m个点处引出m条道路，所以顶层的点拆点后的边的容量不能修改（其实改了也没影响），同时还应把底层的Xj连向汇点的边的容量放宽，为了充分利用规则1中已经建好的图，扫一遍边集修改就行了。
规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。
分析：这里类比规则2，可以再把相邻点之间的边的容量的限制放宽（由1修改为INF或者m）。注意源点向顶层Xi的边不能改。
利用原有的边建图会更方便更快。
代码：
总时间耗费: 7ms
总内存耗费: 364B
总内存耗费: 364B
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;const int maxn = 400 + 10;
const int INF = 1000000007;int n, m, s, t, delta;
int map[maxn][maxn], ID[maxn][maxn];struct Edge {int from, to, cap, flow, cost;
};vector<Edge> edges;
vector<int> G[maxn];void AddEdge(int from, int to, int cap, int cost) {edges.push_back((Edge){from, to, cap, 0, cost});edges.push_back((Edge){to, from, 0, 0, -cost});int sz = edges.size();G[from].push_back(sz-2);G[to].push_back(sz-1);
}bool inq[maxn];
int a[maxn], d[maxn], p[maxn];bool BellmanFord(int& flow, int& cost) {for(int i = s; i <= t; i++) d[i] = INF;memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;queue<int> Q;Q.push(s);while(!Q.empty()) {int x = Q.front(); Q.pop();inq[x] = 0;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[e.to] > d[x] + e.cost) {d[e.to] = d[x] + e.cost;p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap-e.flow);if(!inq[e.to]) {Q.push(e.to);inq[e.to] = 1;}}}}if(d[t] == INF) return 0;flow += a[t];cost += d[t] * a[t];int x = t;while(x != s) {edges[p[x]].flow += a[t];edges[p[x]^1].flow -= a[t];x = edges[p[x]].from;}return 1;
}void MincostMaxflow() {int flow = 0, cost = 0;while(BellmanFord(flow, cost));cout << -cost << endl;
}void init() {cin >> m >> n;for(int i = 1; i <= n; i++)for(int j = 1; j < m+i; j++) {ID[i][j] = ++t;cin >> map[i][j];}delta = t;t = t * 2 + 1;
}void init_1() {for(int x = 1; x <= n; x++)for(int y = 1; y < x+m; y++) {int& id = ID[x][y];AddEdge(id, id+delta, 1, -map[x][y]);if(x == 1) AddEdge(s, id, 1, 0);if(x == n) AddEdge(id+delta, t, 1, 0); //key1else {AddEdge(id+delta, ID[x+1][y], 1, 0);AddEdge(id+delta, ID[x+1][y+1], 1, 0);}}
}void init_2() {for(int x = 1; x <= delta; x++) for(int i = 0; i < G[x].size(); i++) //key 2if(edges[G[x][i]].to == x + delta) {edges[G[x][i]].cap = m;break;}for(int y = 1; y < n+m; y++) {int x = ID[n][y] + delta;for(int i = 0; i < G[x].size(); i++) if(edges[G[x][i]].to == t) edges[G[x][i]].cap = m; //key 4}for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;
}void init_3() {for(int i = 0; i < edges.size(); i++) {Edge& e = edges[i];e.flow = 0;if(e.cap && e.from != s) e.cap = m; //key 3}
}void debug() {for(int i = 0; i < edges.size(); i++) {Edge& e = edges[i];if(e.cap) printf("%d %d %d %d\n", e.from, e.to, e.cap, e.cost);}
}void regulation_1() {init_1();//debug();MincostMaxflow();
}void regulation_2() {init_2();//debug();MincostMaxflow();
}void regulation_3() {init_3();//debug();MincostMaxflow();
}int main() {init();regulation_1();regulation_2();regulation_3();return 0;
}
