• <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 閱讀(3348) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告
            久久天天躁狠狠躁夜夜avapp| 亚洲国产精品狼友中文久久久| 狠狠色丁香久久婷婷综合图片 | 国产精品久久久久乳精品爆| 91精品国产高清久久久久久91| 中文字幕一区二区三区久久网站| 94久久国产乱子伦精品免费| 久久婷婷人人澡人人| 一本一本久久A久久综合精品| 久久亚洲国产欧洲精品一| 日韩久久无码免费毛片软件| 亚洲精品乱码久久久久久按摩| 韩国三级中文字幕hd久久精品| 亚洲精品NV久久久久久久久久| 久久精品国产99国产精品澳门| 久久99精品国产麻豆宅宅| 色综合久久综精品| 亚洲αv久久久噜噜噜噜噜| 国产精品99久久不卡| 国产精品视频久久久| 精品国产乱码久久久久软件| 日日狠狠久久偷偷色综合96蜜桃| 久久久久国产精品| 久久精品无码专区免费东京热| 久久久久久精品免费看SSS| 久久www免费人成看国产片| 99精品久久精品一区二区| 亚洲中文字幕伊人久久无码| 久久精品国产一区二区三区不卡| 久久婷婷久久一区二区三区| 国产综合久久久久久鬼色| 亚洲AV无码久久精品色欲| 欧美日韩精品久久久免费观看| 久久久久亚洲AV成人网| 久久se精品一区二区影院| 99久久精品免费看国产免费| 亚洲欧美日韩精品久久| 91亚洲国产成人久久精品| 久久激情亚洲精品无码?V| 99久久www免费人成精品| 久久精品一区二区影院|