題意：
? ? ?給一個n*n的矩陣，從左上角走到右下角，的最大收益，可以走k次，每個格子的價值只能取一次，但是可以走多次。


思路：
? ? ? 比較簡單的一個費用流題目，直接拆點，拆開的點之間連接兩條邊，一條是流量1費用是這個點的價值，另一條是流量k-1費用是0，然后就是當前這個點連接右下方的點，然后在虛擬出超級遠點和匯點限流用的，比較簡單，不解釋了。




#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 5100
#define N_edge 200000
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int from ,to ,cost ,flow ,next;
}STAR;


STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mer[N_node];


void add(int a ,int b ,int c ,int d)
{
? ? E[++tot].from = a;
? ? E[tot].to = b;
? ? E[tot].cost = c;
? ? E[tot].flow = d;
? ? E[tot].next = list[a];
? ? list[a] = tot;


? ? E[++tot].from = b;
? ? E[tot].to = a;
? ? E[tot].cost = -c;
? ? E[tot].flow = 0;
? ? E[tot].next = list[b];
? ? list[b] = tot;


}


bool spfa(int s ,int t ,int n)
{
? ? for(int i = 0 ;i <= n ;i ++)
? ? s_x[i] = -INF;
? ? int mark[N_node] = {0};
? ? queue<int>q;
? ? q.push(s);
? ? s_x[s] = 0;
? ? mark[s] = 1;
? ? memset(mer ,255 ,sizeof(mer));
? ? while(!q.empty())
? ? {
? ? ? ? int xin ,tou;
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? mark[tou] = 0;
? ? ? ? for(int k = list[tou] ;k ;k = E[k].next)
? ? ? ? {
? ? ? ? ? ? xin = E[k].to;
? ? ? ? ? ? if(s_x[xin] < s_x[tou] + E[k].cost && E[k].flow)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x[xin] = s_x[tou] + E[k].cost;
? ? ? ? ? ? ? ? mer[xin] = k;
? ? ? ? ? ? ? ? if(!mark[xin])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }


? ? ? ? }
? ? }
? ? return mer[t] != -1;
}


int M_M_Flow(int s ,int t ,int n)
{
? ? int maxflow = 0 ,maxcost = 0 ,minflow;
? ? while(spfa(s ,t ,n))
? ? {
? ? ? ? minflow = INF;
? ? ? ? for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
? ? ? ? if(minflow > E[i].flow) minflow = E[i].flow;
? ? ? ? for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
? ? ? ? {
? ? ? ? ? ? E[i].flow -= minflow;
? ? ? ? ? ? E[i^1].flow += minflow;
? ? ? ? ? ? maxcost += minflow * E[i].cost;
? ? ? ? }
? ? ? ? maxflow += minflow;
? ? }
? ? return maxcost;
}


int main ()
{
? ? int n ,k ,i ,j ,Ans ,num;
? ? while(~scanf("%d %d" ,&n ,&k))
? ? {
? ? ? ? memset(list ,0 ,sizeof(list)) ,tot = 1;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&num);
? ? ? ? ? ? add((i - 1) * n + j ,(i - 1) * n + j + n * n ,num ,1);
? ? ? ? ? ? add((i - 1) * n + j ,(i - 1) * n + j + n * n ,0 ,k - 1);
? ? ? ? }


? ? ? ? add(0 ,1 ,0 ,k);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? {
? ? ? ? ? ? if(i <= n - 1) add((i - 1) * n + j + n * n ,i * n + j ,0 ,k);
? ? ? ? ? ? if(j <= n - 1) add((i - 1) * n + j + n * n ,(i - 1) * n + j + 1 ,0 ,k);
? ? ? ? }
? ? ? ? add(n * n * 2 ,n * n * 2 + 1 ,0 ,k);
? ? ? ? Ans = M_M_Flow(0 ,n * n * 2 + 1 ,n * n * 2 + 1);
? ? ? ? printf("%d\n" ,Ans);
? ? }
? ? ?return 0;
}

總結

以上是生活随笔為你收集整理的POJ3422简单费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。