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

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>
            欧美大片免费看| 亚洲一区影音先锋| 免费亚洲电影在线| 巨胸喷奶水www久久久免费动漫| 国内精品久久久久久久果冻传媒 | 亚洲一区网站| 亚洲在线播放电影| 国产午夜精品在线| 欧美成人一区在线| 欧美视频一区二区三区四区| 久久9热精品视频| 麻豆精品精品国产自在97香蕉| 影音先锋日韩精品| 亚洲区第一页| 国产精品久久久一本精品| 香蕉久久夜色| 久久综合九色综合久99| 一区二区三区日韩在线观看| 亚洲欧美在线免费| 亚洲电影观看| 亚洲天堂免费观看| 亚洲国产成人不卡| 一区二区三区不卡视频在线观看| 国产一区二区| 亚洲伦理一区| 尤物网精品视频| 亚洲日本一区二区| 国产亚洲aⅴaaaaaa毛片| 亚洲国产精品毛片| 国产真实精品久久二三区 | 亚洲永久精品大片| 久久美女性网| 亚洲欧洲av一区二区三区久久| 久久久久.com| 欧美亚洲日本国产| 欧美日本视频在线| 美女图片一区二区| 国产区在线观看成人精品| 欧美黄色免费网站| 国产一区二区在线观看免费播放 | 在线视频欧美日韩| 久久视频国产精品免费视频在线| 亚洲欧美日韩人成在线播放| 欧美福利一区| 欧美成人一品| 激情综合网激情| 亚洲欧美日韩国产一区| 一区二区精品| 欧美国产激情二区三区| 久久综合激情| 狠狠色狠狠色综合系列| 亚洲欧美日韩高清| 亚洲欧美一区二区精品久久久| 欧美激情女人20p| 亚洲国产天堂久久国产91| 在线观看91精品国产麻豆| 欧美在线看片| 久久激情五月激情| 国产午夜精品一区二区三区欧美 | 欧美va亚洲va国产综合| 精久久久久久久久久久| 新片速递亚洲合集欧美合集| 亚洲一区二区综合| 国产精品v亚洲精品v日韩精品 | 欧美插天视频在线播放| 欧美激情一区二区| 亚洲人成人99网站| 欧美不卡高清| 日韩天堂在线观看| 亚洲欧美日韩一区二区三区在线观看 | 久久综合中文色婷婷| 蜜桃久久av一区| 亚洲激情在线观看视频免费| 免费日本视频一区| 亚洲精品在线三区| 亚洲一区视频在线| 国产三级欧美三级| 久久久久久电影| 国产精品99免视看9| 亚洲美女电影在线| 亚洲欧美不卡| 黄色精品一二区| 久久免费少妇高潮久久精品99| 欧美成人精品在线观看| 亚洲品质自拍| 欧美视频一区二区三区…| 亚洲深夜福利视频| 乱中年女人伦av一区二区| 亚洲区一区二区三区| 欧美午夜精品理论片a级按摩 | 国产欧美另类| 欧美成人激情视频免费观看| 日韩午夜免费| 久久高清一区| 亚洲精品乱码久久久久久| 欧美色一级片| 久久亚洲捆绑美女| 99re6这里只有精品视频在线观看| 亚洲一区二区精品在线| 精品不卡一区二区三区| 欧美日韩一区二区三区四区在线观看| 亚洲欧美日韩一区二区三区在线观看 | 亚洲欧美不卡| 亚洲成人在线免费| 久久久久久久波多野高潮日日| 亚洲精品美女在线观看| 国产精品推荐精品| 欧美成人一区二区三区| 午夜精品短视频| 亚洲精品乱码久久久久久黑人 | 亚洲欧美日韩中文播放| 亚洲福利视频网站| 国产农村妇女毛片精品久久莱园子| 久久一区免费| 欧美一区免费| 亚洲视频图片小说| 亚洲精品中文字幕女同| 你懂的一区二区| 久久精视频免费在线久久完整在线看 | 米奇777超碰欧美日韩亚洲| 亚洲综合精品| 日韩一级黄色片| 亚洲福利电影| 欧美a级一区| 久久色中文字幕| 欧美一级视频| 午夜在线精品偷拍| 亚洲综合国产精品| 一本色道久久综合狠狠躁篇的优点 | 欧美黄色日本| 欧美va亚洲va日韩∨a综合色| 久久裸体艺术| 久久亚洲色图| 玖玖玖国产精品| 久久久久久久久久久久久9999| 午夜伦欧美伦电影理论片| 一区二区欧美精品| 在线视频精品| 亚洲无线视频| 亚洲综合第一| 欧美在线一级va免费观看| 午夜在线一区二区| 欧美在线free| 久久婷婷蜜乳一本欲蜜臀| 久久麻豆一区二区| 免费人成网站在线观看欧美高清| 老司机午夜精品视频| 免费成人在线视频网站| 欧美国产亚洲精品久久久8v| 欧美高清视频一区二区三区在线观看| 欧美不卡高清| 亚洲国内精品| 一本色道久久综合狠狠躁篇怎么玩 | 一本久道久久久| 亚洲一区二区三区精品在线观看| 亚洲制服av| 欧美在线免费视屏| 久久综合导航| 欧美激情一区二区在线| 国产精品扒开腿做爽爽爽视频 | 欧美国产视频日韩| 欧美午夜无遮挡| 国产一级揄自揄精品视频| 亚洲国产精品va| 亚洲视频一区| 欧美中文字幕在线观看| 你懂的国产精品| 一本色道久久综合一区| 欧美一区二视频| 欧美激情精品久久久久| 国产精品网站视频| 亚洲国产网站| 亚洲欧美亚洲| 亚洲国产精彩中文乱码av在线播放| 99亚洲精品| 久久精品免费看| 欧美日韩在线综合| 一色屋精品视频在线观看网站 | 国产丝袜一区二区三区| 亚洲精品欧洲精品| 久久久精品动漫| 日韩亚洲欧美综合| 久久精品国产69国产精品亚洲| 欧美久久久久久久久久| 国外成人网址| 亚洲小视频在线| 欧美激情1区2区3区| 亚洲主播在线| 欧美日韩亚洲一区二区三区在线观看 | 亚洲日本中文| 久久久久久久97| 国产精品久久久久一区二区三区| 亚洲高清不卡在线观看| 欧美在线免费视屏| 一本色道综合亚洲| 欧美精品免费在线| 亚洲国产乱码最新视频| 久久精品视频免费| 亚洲综合精品自拍| 国产精品久久国产精品99gif|