• <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 閱讀(3359) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告
            久久中文精品无码中文字幕| 久久久久99这里有精品10| 久久午夜伦鲁片免费无码| 久久国产精品国产自线拍免费| 91精品国产高清久久久久久91| 久久精品国产亚洲av麻豆蜜芽| 91视频国产91久久久| 久久亚洲国产成人精品无码区| 九九久久自然熟的香蕉图片| 久久久久久国产精品无码下载| 久久99热只有频精品8| 思思久久99热免费精品6| 人人狠狠综合久久亚洲88| 无码伊人66久久大杳蕉网站谷歌| 久久国产福利免费| 丁香狠狠色婷婷久久综合| 久久天天躁狠狠躁夜夜2020一| 狠狠色综合网站久久久久久久| 日韩精品久久无码人妻中文字幕| 伊人久久五月天| 欧美日韩精品久久久久| 热99re久久国超精品首页| 国内精品久久人妻互换| 久久午夜无码鲁丝片| 成人午夜精品无码区久久| 无码人妻久久一区二区三区蜜桃| 久久国产综合精品五月天| 成人精品一区二区久久| 996久久国产精品线观看| AV无码久久久久不卡蜜桃 | 精品无码久久久久久久动漫| 无码国内精品久久人妻| 亚洲国产精品无码久久一线 | 国产精品永久久久久久久久久| 国产精品久久一区二区三区 | 久久无码人妻一区二区三区午夜 | 久久精品国产只有精品66| 久久久久99精品成人片牛牛影视| 国产成人精品久久二区二区| 久久久久四虎国产精品| 91精品国产91热久久久久福利|