• <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>
            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 閱讀(3345) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告
            久久精品国产亚洲AV香蕉| 国产精品久久久久国产A级| 91麻精品国产91久久久久| 99久久免费只有精品国产| 性做久久久久久免费观看| 久久婷婷午色综合夜啪| 亚洲av伊人久久综合密臀性色| 久久国产亚洲高清观看| 久久久久这里只有精品| 一本久道久久综合狠狠爱| 久久大香香蕉国产| 无码精品久久一区二区三区| 蜜臀av性久久久久蜜臀aⅴ麻豆| 欧美亚洲另类久久综合| 噜噜噜色噜噜噜久久| 亚洲精品高清久久| 囯产精品久久久久久久久蜜桃 | 无码人妻精品一区二区三区久久 | 久久99久国产麻精品66| 国产一区二区三区久久| 免费久久人人爽人人爽av| 国产福利电影一区二区三区久久久久成人精品综合 | 99久久精品影院老鸭窝| 色综合久久久久综合99| 成人免费网站久久久| 久久中文字幕人妻熟av女| 久久国产成人亚洲精品影院| 日本人妻丰满熟妇久久久久久| 久久精品国产第一区二区| 狠狠色丁香婷综合久久| 久久夜色精品国产噜噜亚洲AV| 亚洲精品国精品久久99热| 久久国产午夜精品一区二区三区| 久久精品男人影院| 久久亚洲国产精品一区二区| 久久久久亚洲AV成人片| 久久夜色精品国产网站| 久久夜色精品国产噜噜麻豆| AV狠狠色丁香婷婷综合久久| 久久A级毛片免费观看| 亚洲精品蜜桃久久久久久|