我真的好烦这个addEdge啊，每次看到这个就晕
没怎么看懂，不想看
题意：对于N*N的数组，给一个k，从（1，1）走到（N，N），走k次，走到每个点权值加上当前这个点的权值，之后这个点权值为0，求最大权值
对点进行拆分建图，一个点拆为两个点a和b，在a和b之间建一条花费为输入值容量为1的边，然后再建一条花费为0容量为k-1的边，对b点对于其右边和下边都建立一条容量为k花费为0的边，加入超级源点和汇点，花费为0容量为k，由此套模板就可以了
#include<iostream> #include<string.h> #include<stdio.h> #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int nMax = 5005; const int eMax = 20050; struct { int v, cap, cost, next, re; } edge[eMax]; int n, ans; int k, edgeHead[nMax]; int que[nMax], pre[nMax], dis[nMax]; bool vis[nMax]; void addEdge(int u, int v, int ca, int co) { 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; //一开始用堆栈,用了980多MS,囧... for(i = 0; i <= n; 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[n] <= 0) return false; return true; } void end() { int u, p; for(u = n; 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; } } int main() { int N, K, map[52][52], i, j; scanf("%d%d", &N, &K); for(i = 1; i <= N; i ++) for(j = 1; j <= N; j ++) scanf("%d", &map[i][j]); for(k = i = 1; i <= N; i ++) for(j = 1; j <= N; j ++) { int a = (i-1)*N + j; int b = a + N*N; addEdge(a, b, 1, map[i][j]); //拆点，连2条边。 addEdge(a, b, K, 0); if(i < N) addEdge(b, a+N, K, 0); // 向下的点连边 if(j < N) addEdge(b, a+1, K, 0); // 向右的点连边 } n = 2*N*N + 1; addEdge(0, 1, K, 0); // 连源点的边。 addEdge(2*N*N, n, K, 0); // 连汇点的边。 ans = 0; while(spfa()) end(); printf("%d\n", ans); return 0; }
