TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1952
  • 問題
  • P1952【线性规划与网络流24题 17】运输问题
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    W公司有m个仓库和n 个零售商店。第i 个仓库有ai个单位的货物;第j个零售商店需要bj个单位的货物。
    货物供需平衡,即sigma(ai)==sigma(bj)。
    从第i个仓库运送每单位货物到第j个零售商店的费用为Cij。试设计一个将仓库中所有货物运送到零售商店的运输方案,
    使总运输费用最少。

    入力形式

    第1行有2 个正整数m和n,分别表示仓库数和零售商店数。
    接下来的一行中有m个正整数ai,1≤i≤m,表示第i个仓库有ai个单位的货物。
    再接下来的一行中有n个正整数bj,1≤j≤n,表示第j个零售商店需要bj个单位的货物。
    接下来的m行,每行有n个整数,表示从第i个仓库运送每单位货物到第j个零售商店的费用Cij。

    出力形式

    程序运行结束时,将计算出的最少运输费用和最多运输费用输出

    サンプル入力

    2 3
    220 280
    170 120 210
    77 39 105
    150 186 122

    サンプル出力

    48500
    69140

    ヒント

    1<=n,m<=100

    0<=Ai,Bi,Cij<=1000


    ソース  感谢 Wo_ai_WangYuan 放上题目和数据