青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 18,  comments - 5,  trackbacks - 0
一、題目描述

Description

Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy has M supply places (marked from 1 to M), each provides K different kinds of goods (marked from 1 to K). Once shopkeepers order goods, Dearboy should arrange which supply place provide how much amount of goods to shopkeepers to cut down the total cost of transport.

It's known that the cost to transport one unit goods for different kinds from different supply places to different shopkeepers may be different. Given each supply places' storage of K kinds of goods, N shopkeepers' order of K kinds of goods and the cost to transport goods for different kinds from different supply places to different shopkeepers, you should tell how to arrange the goods supply to minimize the total cost of transport.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, K (0 < N, M, K < 50), which are described above. The next N lines give the shopkeepers' orders, with each line containing K integers (there integers are belong to [0, 3]), which represents the amount of goods each shopkeeper needs. The next M lines give the supply places' storage, with each line containing K integers (there integers are also belong to [0, 3]), which represents the amount of goods stored in that supply place.

Then come K integer matrices (each with the size N * M), the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in the k-th matrix represents the cost to transport one unit of k-th goods from the j-th supply place to the i-th shopkeeper.

The input is terminated with three "0"s. This test case should not be processed.

Output

For each test case, if Dearboy can satisfy all the needs of all the shopkeepers, print in one line an integer, which is the minimum cost; otherwise just output "-1".

Sample Input

1 3 3
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1
1 1 1
3
2
20
0 0 0

Sample Output

4
-1


二、分析
      一個的最小費用最大流問題,詳細算法:最小費用最大流
三、代碼

  1#include<iostream>
  2#include<queue>
  3using namespace std;
  4int n, m, kind;
  5int s, t;
  6int order[51][51];
  7int store[51][51];
  8int cost[51][51][51];
  9int c[102][102];
 10int f[102][102];
 11int b[102][102];
 12int p[102];
 13int d[102];
 14bool visit[102]; //表示spfa中點是否在隊列中
 15void spfa() //求Gf的最短路
 16{
 17    queue<int> q;
 18    memset(visit, 0sizeof(visit));
 19    q.push(s);
 20    visit[s] = true;
 21    while(!q.empty())
 22    {
 23        int u = q.front();
 24        visit[u] = false;
 25        q.pop();
 26        for(int v=0; v<=n+m+1; v++)
 27            if(c[u][v] > f[u][v] && d[v] > d[u] + b[u][v])
 28            {
 29                d[v] = d[u] + b[u][v];
 30                p[v] = u;
 31                if(!visit[v])
 32                {
 33                    q.push(v);
 34                    visit[v] = true;
 35                }

 36            }

 37    }

 38}

 39void mcmf()
 40{
 41    while(1)
 42    {
 43        memset(p, -1sizeof(p));
 44        for(int i=1; i<=n+m+1; i++)
 45            d[i] = 100000;
 46        d[s] = 0;
 47        spfa();
 48        if(p[t] == -1//表示已無增廣路
 49            break;
 50        int minf = INT_MAX;
 51        int it = t;
 52        while(p[it] != -1)
 53        {
 54            minf = min(minf, c[p[it]][it] - f[p[it]][it]);
 55            it = p[it];
 56        }

 57        it = t;
 58        while(p[it] != -1)
 59        {
 60            f[p[it]][it] += minf;
 61            f[it][p[it]] = -f[p[it]][it];
 62            it = p[it];
 63        }

 64    }

 65}

 66int main()
 67{
 68    while(1)
 69    {
 70        scanf("%d%d%d"&n, &m, &kind);
 71        if(n==0 && m==0 && kind==0)
 72            break;
 73        for(int i=1; i<=n; i++)
 74            for(int j=1; j<=kind; j++)
 75                scanf("%d"&order[i][j]);
 76        for(int i=1; i<=m; i++)
 77            for(int j=1; j<=kind; j++)
 78                scanf("%d"&store[i][j]);
 79        for(int i=1; i<=kind; i++)
 80            for(int j=1; j<=n; j++)
 81                for(int k=1; k<=m; k++)
 82                    scanf("%d"&cost[i][k][j]);
 83        s = 0; t = m+n+1;
 84        int res = 0;
 85        bool flag = true;
 86        for(int i=1; i<=kind; i++)
 87        {
 88            memset(c, 0sizeof(c));
 89            for(int j=1; j<=m; j++)
 90                c[s][j] = store[j][i];
 91            for(int j=1; j<=m; j++)
 92                for(int k=1; k<=n; k++)
 93                    c[j][k+m] = store[j][i];
 94            for(int j=1; j<=n; j++)
 95                c[j+m][t] = order[j][i];
 96            memset(b, 0sizeof(b));
 97            for(int j=1; j<=m; j++)
 98                for(int k=1; k<=n; k++)
 99                {
100                    b[j][k+m] = cost[i][j][k];
101                    b[k+m][j] = -b[j][k+m]; //負費用,表示回流會減小費用
102                }

103            memset(f, 0sizeof(f));
104            mcmf();
105            for(int j=1; j<=n; j++)
106                if(c[j+m][t] != f[j+m][t])
107                {
108                    flag = false;
109                    break;
110                }

111            if(!flag) break;
112            for(int j=1; j<=m; j++)
113                for(int k=1; k<=n; k++)
114                    res += f[j][m+k] * b[j][m+k];
115        }

116        if(flag)
117            printf("%d\n", res);
118        else
119            printf("-1\n");
120    }

121}
posted on 2009-06-30 22:09 Icyflame 閱讀(3363) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产一区视频在线观看免费| 欧美日韩精品免费观看视频完整| 欧美精品国产精品| 日韩亚洲欧美中文三级| 亚洲激情网址| 欧美激情一区二区三区四区| 一区二区三区国产在线观看| 亚洲综合色婷婷| 国产主播喷水一区二区| 欧美成人午夜剧场免费观看| 欧美aaa级| 亚洲图片在区色| 香蕉成人久久| 亚洲精品在线二区| 亚洲一区二区在线播放| 激情欧美日韩| 日韩视频三区| 国产夜色精品一区二区av| 欧美大片第1页| 国产精品高精视频免费| 久久综合狠狠综合久久综合88| 免费观看一级特黄欧美大片| 亚洲网站啪啪| 欧美在线免费| 亚洲午夜一区| 免费不卡在线观看av| 亚洲欧美日韩综合aⅴ视频| 久久久久99精品国产片| 亚洲先锋成人| 美女国产精品| 午夜精品www| 欧美成人一区二区三区片免费| 午夜欧美视频| 欧美v亚洲v综合ⅴ国产v| 在线亚洲观看| 国产午夜精品一区二区三区欧美| 亚洲精品乱码久久久久久黑人| 欧美gay视频激情| 国产精品va在线| 欧美激情偷拍| 国产综合18久久久久久| 99国产精品久久| 在线亚洲一区二区| 亚洲激情在线观看视频免费| 一本色道久久综合精品竹菊| 亚洲国产91色在线| 亚洲欧美文学| 亚洲欧美区自拍先锋| 欧美电影在线播放| 欧美mv日韩mv亚洲| 国产亚洲一区在线| 午夜精彩国产免费不卡不顿大片| 夜夜嗨av色综合久久久综合网| 午夜精品久久久| 亚洲午夜精品久久久久久app| 日韩写真视频在线观看| 欧美日韩成人在线观看| 欧美凹凸一区二区三区视频| 国产婷婷色一区二区三区在线 | 欧美电影美腿模特1979在线看| 久久国产精品黑丝| 国产视频一区二区在线观看 | 欧美在线亚洲在线| 久久国产乱子精品免费女| 国产精品乱码妇女bbbb| 一区二区三区欧美激情| 亚洲视频在线二区| 国产精品v欧美精品v日韩| 在线亚洲免费视频| 亚洲综合清纯丝袜自拍| 国产精品国产| 亚洲欧美电影院| 亚洲欧美中文日韩在线| 国产精品久久久久久av福利软件| 一区二区三区免费观看| 亚洲尤物视频网| 国产精品免费视频观看| 亚洲欧美日韩在线综合| 欧美在线免费| 在线欧美日韩精品| 欧美国产日本在线| 在线一区二区三区四区五区| 亚洲欧美另类综合偷拍| 国产日韩欧美另类| 久久在线免费观看视频| 亚洲黄一区二区三区| 正在播放亚洲| 国产精品一国产精品k频道56| 性娇小13――14欧美| 国产精品色网| 免费欧美在线视频| 亚洲欧洲精品天堂一级| 亚洲三级毛片| 亚洲一区国产精品| 国内成人精品一区| 欧美大片专区| 午夜精品久久久久久久男人的天堂| 久久精品国产99国产精品澳门| 亚洲成人在线网| 欧美三级电影一区| 久久精品一区| 日韩午夜在线| 久久久久久久一区二区| 夜夜嗨av色综合久久久综合网| 国产欧美精品一区aⅴ影院| 久久亚洲影音av资源网| 一区二区三区黄色| 美女诱惑黄网站一区| 亚洲欧美国产高清| 在线观看欧美日本| 亚洲黄色在线看| 夜夜嗨av一区二区三区免费区| 欧美a级在线| 国产精品综合| 欧美激情一区二区三区在线视频| 亚洲三级影院| 国产一区二区欧美| 欧美视频免费在线观看| 免费不卡在线观看| 欧美在线三级| 亚洲欧美另类在线观看| 亚洲美女免费精品视频在线观看| 蜜臀av性久久久久蜜臀aⅴ| 噜噜噜噜噜久久久久久91 | 亚洲精品无人区| 精品成人国产| 国产欧美日韩激情| 国产精品国产三级国产普通话三级 | 国产精品欧美一区二区三区奶水| 久久久免费精品视频| 亚洲永久网站| 一区二区三区高清不卡| 亚洲精品永久免费| 亚洲国产另类久久精品| 免费欧美在线视频| 欧美xxx成人| 欧美国产第一页| 欧美成年网站| 免费不卡在线视频| 免费欧美日韩| 亚洲二区视频| 亚洲国产婷婷香蕉久久久久久99| 久久这里只有精品视频首页| 先锋资源久久| 久久国产天堂福利天堂| 久久精品视频在线看| 久久久久一区二区三区四区| 久久黄色网页| 老鸭窝毛片一区二区三区| 麻豆av一区二区三区| 亚洲免费人成在线视频观看| 欧美凹凸一区二区三区视频| 亚洲人成网站在线播| 亚洲电影第1页| 亚洲人成艺术| 一卡二卡3卡四卡高清精品视频| 亚洲精品小视频在线观看| 亚洲视频免费在线| 亚洲欧美久久久| 久久久久久精| 欧美—级高清免费播放| 欧美视频中文一区二区三区在线观看| 欧美视频在线免费看| 国产一区91| 亚洲国产欧美一区二区三区同亚洲| 亚洲日韩欧美视频一区| 亚洲一本大道在线| 久久精品在线播放| 亚洲国产一区二区三区a毛片 | 欧美一区二区三区的| 久久香蕉国产线看观看av| 亚洲电影激情视频网站| 一道本一区二区| 久久国产免费看| 欧美一区二区三区四区在线观看| 欧美大色视频| 欧美一区二区精品在线| 久久伊人免费视频| 亚洲欧洲在线播放| 亚洲欧洲日产国产网站| 亚洲欧美激情视频在线观看一区二区三区 | 欧美日韩国产综合视频在线观看中文| 欧美视频在线播放| 亚洲成在人线av| 欧美亚洲免费在线| 亚洲欧洲日韩在线| 欧美一区二区精品| 欧美日韩成人| 亚洲福利国产| 欧美一区二区三区日韩视频| 欧美激情在线有限公司| 午夜宅男久久久| 欧美日韩高清在线| 亚洲国产精品va在看黑人| 午夜精品久久久久久久男人的天堂| 免费久久99精品国产自| 午夜精彩视频在线观看不卡| 欧美另类videos死尸| 亚洲激情第一页| 久久人91精品久久久久久不卡|