【算法】最小费用最大流(费用流)
【题解】
费用流&＃xff1a;http://www.cnblogs.com/onioncyc/p/6496532.html
本题构图&＃xff1a;
在有限的k次行走中尽可能多的拿到数字&＃xff0c;明显的取舍问题&＃xff0c;可以用网络流解决。
一共只有k次行走&＃xff0c;因此流量至多为k。
而在起点到终点的所有最大流应该使价值最大化(取得数字最大)&＃xff0c;因此就可以构图了。
为每个节点x复制一个分点x’&＃xff0c;从x向x&＃39;连一条容量1&＃xff0c;费用-num[x]的边&＃xff08;限制数字只能取一次&＃xff0c;代价变成负数就可以跑最小费用&＃xff09;
注意&＃xff1a;因为每个点其实可以重复经过&＃xff0c;但数字不能重复取&＃xff0c;因此再从x向x&＃39;连一条容量k(相当于inf)&＃xff0c;费用0的边。
从x’向右和下连容量k&＃xff0c;费用0的边。
S向第一格顶连容量k&＃xff0c;费用0的边。
最后一格底向T连容量k&＃xff0c;费用0的边。
构图完毕。
本题的核心是满足走k次(最大流)的前提下取的数字尽可能大(费用尽可能小)&＃xff0c;流只是前提&＃xff0c;关键在每个节点那条带费用的边。
费用为负数的边越小当然越能吸引水流过去&＃xff0c;最后就能跑出最小费用流。
---
注意数组范围&＃xff01;
spfa的vis只决定进不进队列&＃xff0c;不妨碍松弛&＃xff01;
#include
#include
#include
using namespace std;
const int inf&＃61;0x3f3f3f3f,maxn&＃61;60,maxN&＃61;5100;
int n,N,k,p[maxn][maxn],first[maxN],tot&＃61;1,d[maxN],q[1010],S,T,ans;
bool vis[maxN];
struct edge{int from,v,flow,cost;}e[30000];
void insert(int u,int v,int flow,int cost)
{tot&＃43;&＃43;;e[tot].v&＃61;v;e[tot].flow&＃61;flow;e[tot].cost&＃61;cost;e[tot].from&＃61;first[u];first[u]&＃61;tot;tot&＃43;&＃43;;e[tot].v&＃61;u;e[tot].flow&＃61;0;e[tot].cost&＃61;-cost;e[tot].from&＃61;first[v];first[v]&＃61;tot;
}
bool spfa()
{memset(d,0x3f,4*(N&＃43;N&＃43;2));memset(vis,0,N&＃43;N&＃43;2);int head&＃61;0,tail&＃61;1;q[0]&＃61;T;vis[T]&＃61;1;d[T]&＃61;0;while(head!&＃61;tail){int x&＃61;q[head&＃43;&＃43;];if(head>&＃61;1001)head&＃61;0;for(int i&＃61;first[x];i;i&＃61;e[i].from)if(e[i^1].flow&&d[x]&＃43;e[i^1].cost<d[e[i].v]){d[e[i].v]&＃61;d[x]&＃43;e[i^1].cost;if(!vis[e[i].v]){q[tail&＃43;&＃43;]&＃61;e[i].v;if(tail>&＃61;1001)tail&＃61;0;vis[e[i].v]&＃61;1;}}vis[x]&＃61;0;}return d[S]<inf;
}
int dfs(int x,int a)
{vis[x]&＃61;1;if(x&＃61;&＃61;T||a&＃61;&＃61;0)return a;int flow&＃61;0,f;for(int i&＃61;first[x];i;i&＃61;e[i].from)if(!vis[e[i].v]&&d[x]&＃61;&＃61;e[i].cost&＃43;d[e[i].v]&&(f&＃61;dfs(e[i].v,min(a,e[i].flow)))>0){e[i].flow-&＃61;f;e[i^1].flow&＃43;&＃61;f;ans&＃43;&＃61;e[i].cost*f;a-&＃61;f;flow&＃43;&＃61;f;if(a&＃61;&＃61;0)break;}return flow;
}
int main()
{scanf("%d%d",&n,&k);N&＃61;n*n;S&＃61;0,T&＃61;N&＃43;N&＃43;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){int x;p[i][j]&＃61;(i-1)*n&＃43;j;scanf("%d",&x);insert(p[i][j],p[i][j]&＃43;N,1,-x);insert(p[i][j],p[i][j]&＃43;N,k,0);//建立仅供行走的无价值边
}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){if(j
}
#include
#include
#include
using namespace std;
int n,k,S,T;namespace nwf2{const int maxn&＃61;5010,maxm&＃61;10010,inf&＃61;0x3f3f3f3f,N&＃61;5005;int first[maxn],cur[maxn],tot&＃61;1,q[maxn],d[maxn],ans&＃61;0;//
bool vis[maxn];struct edge{int v,f,c,from;}e[maxm*2];void insert(int u,int v,int f,int c){tot&＃43;&＃43;;e[tot].v&＃61;v;e[tot].f&＃61;f;e[tot].c&＃61;c;e[tot].from&＃61;first[u];first[u]&＃61;tot;tot&＃43;&＃43;;e[tot].v&＃61;u;e[tot].f&＃61;0;e[tot].c&＃61;-c;e[tot].from&＃61;first[v];first[v]&＃61;tot;}bool spfa(){memset(d,0x3f,sizeof(d));d[T]&＃61;0;vis[T]&＃61;1;int head&＃61;0,tail&＃61;1;q[head]&＃61;T;while(head!&＃61;tail){//
int x&＃61;q[head&＃43;&＃43;];if(head>N)head&＃61;0;for(int i&＃61;first[x];i;i&＃61;e[i].from)if(e[i^1].f&&d[x]&＃43;e[i^1].c
d[e[i].v]&＃61;d[x]&＃43;e[i^1].c;if(!vis[e[i].v]){if(d[e[i].v]
e[i].f-&＃61;f;e[i^1].f&＃43;&＃61;f;ans&＃43;&＃61;e[i].c*f;flow&＃43;&＃61;f;a-&＃61;f;if(a&＃61;&＃61;0)break;}vis[x]&＃61;0;return flow;}int dinic(){ans&＃61;0;while(spfa()){for(int i&＃61;S;i<&＃61;T;i&＃43;&＃43;)cur[i]&＃61;first[i];dfs(S,inf);}return ans;}
}int main(){scanf("%d%d",&n,&k);S&＃61;0;T&＃61;5001;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){int u;scanf("%d",&u);nwf2::insert((i-1)*n&＃43;j,(i-1)*n&＃43;j&＃43;2500,1,-u);nwf2::insert((i-1)*n&＃43;j,(i-1)*n&＃43;j&＃43;2500,k-1,0);if(i!&＃61;n)nwf2::insert((i-1)*n&＃43;j&＃43;2500,i*n&＃43;j,k,0);if(j!&＃61;n)nwf2::insert((i-1)*n&＃43;j&＃43;2500,(i-1)*n&＃43;j&＃43;1,k,0);}}nwf2::insert(S,1,k,0);nwf2::insert(n*n&＃43;2500,T,k,0);printf("%d",-nwf2::dinic());return 0;
}
京公网安备 11010802041100号