• <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)  編輯 收藏 引用 所屬分類: 解題報告
            午夜精品久久久久久久| 69国产成人综合久久精品| 性欧美大战久久久久久久| 亚洲欧美久久久久9999 | 亚洲综合久久综合激情久久| 青青草国产精品久久久久| 亚洲国产成人精品女人久久久 | 精品久久久久久国产牛牛app| 久久国产福利免费| 久久夜色精品国产网站| 激情综合色综合久久综合| 久久久久av无码免费网| 久久九九亚洲精品| 亚洲精品无码久久久久去q| 久久综合丁香激情久久| 欧美久久久久久| 久久精品草草草| 亚洲中文字幕无码久久2020| 日韩十八禁一区二区久久| 九九99精品久久久久久| 人妻无码精品久久亚瑟影视| 国产精品VIDEOSSEX久久发布| 欧洲人妻丰满av无码久久不卡 | 性做久久久久久久久老女人| 青青青青久久精品国产h| 日韩乱码人妻无码中文字幕久久| 久久综合五月丁香久久激情| 久久国产精品-国产精品| 7777精品久久久大香线蕉| 伊人色综合久久天天网| 久久婷婷五月综合色99啪ak| 91精品日韩人妻无码久久不卡| 欧美黑人又粗又大久久久| 精品久久久久久中文字幕大豆网 | 久久久久久伊人高潮影院| 精品久久久久久久中文字幕| 久久国产精品成人免费| 青草影院天堂男人久久| 精品人妻伦一二三区久久| 国产亚洲成人久久| 久久精品成人欧美大片|