• <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)  編輯 收藏 引用 所屬分類: 解題報告
            日本精品久久久久影院日本 | 久久五月精品中文字幕| 一本一道久久精品综合| 国产AV影片久久久久久| 思思久久99热免费精品6| 精品伊人久久久| 精品一区二区久久久久久久网站| 久久精品国产精品青草| 久久久久噜噜噜亚洲熟女综合 | 91精品国产高清91久久久久久| 久久精品国产精品亚洲精品| 午夜精品久久久久久影视777| 亚洲色欲久久久综合网东京热| 99久久免费国产特黄| 亚洲性久久久影院| 国产精品一久久香蕉产线看| 亚洲第一永久AV网站久久精品男人的天堂AV | 久久综合给合久久国产免费 | 久久精品蜜芽亚洲国产AV| 久久精品成人一区二区三区| 久久这里只有精品18| 亚洲国产成人久久精品99| 青青热久久综合网伊人| 麻豆AV一区二区三区久久| 欧美日韩久久中文字幕| 久久亚洲国产精品123区| 国产精品成人无码久久久久久 | 久久天天躁狠狠躁夜夜躁2014| 久久亚洲国产午夜精品理论片| 亚洲综合熟女久久久30p| 久久综合视频网| 亚洲精品WWW久久久久久 | 国产精品免费久久久久久久久| 久久超乳爆乳中文字幕| 午夜天堂av天堂久久久| 久久国产色av免费看| 久久精品国产免费观看三人同眠| 亚洲精品久久久www| 久久影视综合亚洲| 亚洲欧洲精品成人久久奇米网| 久久综合伊人77777|