C++の道進級--最小費用最大流(善意の投票)

2879:[Noi 2012]グルメフェスティバル
Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 1304  Solved: 702[Submit][Status][Discuss]
Description
CZ市は全国各地の学生を歓迎するために、わざわざ盛大な美食祭を開催した.新鮮な料理が好きな美食客として、Mさんは自然にこの宴会を逃したくない.彼はすぐに美食祭のすべての美食を味わった.しかし、新鮮なものを味わう欲望は満足しにくい.すべての料理がおいしいにもかかわらず、料理人の料理のスピードも速いので、Mさんは自分の机の上にすでに他の人の食卓に並んでいる美食がないのは我慢できないことだと思っています.そこでMさんは料理の順番を研究し始めました.つまり、料理の順番を手配して、学生たちの待ち時間を最短にしました.Mさんは、グルメフェスティバルにはn種類の料理があることを発見しました.注文するたびに、学生一人一人がその中の一つの料理を選ぶことができます.全部でm人のシェフがこれらの料理を作りに来ました.すべての同級生が注文を終えると、料理の制作任務はコック一人一人に割り当てられます.そしてシェフ一人一人が同時に料理を始めます.シェフたちは要求された順番で作り、毎回1人分しか作れません.また、Mさんはもう一つ面白いことを発見しました.このm人のコックはすべてのn種類の料理を作ることができますが、同じ料理に対して、料理人によって制作時間が同じとは限りません.彼は料理を1,2,...,n順番番号、シェフ用1,2,...、m順に番号付けし,j番目のシェフがi番目の料理を作る時間をti,jと記す.Mさんは、同級生一人一人の待ち時間はすべての料理人のために料理を始め、自分の料理が完成するまでの時間の長さだと思っています.言い換えれば、ある同級生が注文した料理があるコックが作ったk番目の料理であれば、彼の待ち時間はこのコックが作る前のk番目の料理の時間の和である.総待ち時間はすべての同級生の待ち時間の和である.今、Mさんはすべての同級生の注文情報を見つけました.pi人の同級生がi番目の料理(i=1、2、...、n)を注文しました.彼が知りたいのは最小の総待ち時間がどれだけなのかです.
Input
入力ファイルの1行目には、料理の数と料理人の数を表す2つの正の整数nとmが含まれています.2行目はn個の正の整数を含み、i番目の数はpiで、i番目の料理を注文した人数を表す.次にn行あり、各行にm個の非負の整数が含まれ、このn行のi行目のj番目の数はti,jであり、j番目のコックがi番目の料理を作るのに要する時間を示す.入力ファイルの行ごとに隣接する2つの数は、1つのスペースで区切られており、行の最後に余分なスペースはありません.
Output
出力には、合計待ち時間の最小値である整数が1行だけ含まれます.
Sample Input
3 2 3 1 1 5 7 3 6 8 9
Sample Output
47 【サンプル説明】シェフ1まず1品2を作り、2品1を作ります.この3品を注文した3人の同級生の待ち時間はそれぞれ3、3+5=8、3+5+5=13です.シェフ2はまず1品1を作り、1品3を作ります.この2品を注文した2人の同級生の待ち時間はそれぞれ7、7+9=16です.総待ち時間は3+8+13+7+16=47です.料理1と3品3はシェフ1がより早く作りますが、これらの料理がすべてシェフ1が作ると、かえって待ち時間が長くなります.上記のように、1品1品と1品3品をシェフ2が作るように調整すれば、シェフ2は暇ではなく、待ち時間が短くなります.より良い注文案がないことを証明することができます.【データ規模及び約定】100%のデータに対して、n<=40、m<=100、p<=800、ti、j<=1000(ここで、p=Σpi、すなわち、オーダーメートの合計数).各セットのデータのn、m、pの値は以下の通りである:試験点番号n m p 1 n=5 m=5 p=10 2 n=40 m=1 p=400 3 n=40 m=2 p=300 4 n=40 m=40 p=40 p=40 n=5 m=40 p=100 6 n=10 m=50 p=200 7 n=20 m=60 p=400 p=40 m=80 p=600 9 n=40 m=100 p=800 10 n=40 m=100 p = 800
HINT
問題:
ダイナミックエッジ
コード:
   

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<queue>
 5 #include<algorithm>
 6 #define maxn 100005
 7 #define T 100001
 8    
 9 using namespace std;
10    
11 int ans,n,tot,m,dis[maxn],head[maxn],cnt=1,c[45],t[45][105],inq[maxn],from[maxn],que[10*maxn];
12    
13 struct ss {int next,to,v,c,from;}e[3000005];
14    
15 void add(int u,int v,int c,int w)
16    {
17     e[++cnt].next=head[u];
18     e[cnt].c=c;
19     e[cnt].v=w;
20     head[u]=cnt;
21     e[cnt].to=v;
22     e[cnt].from=u;  
23    }
24       
25 void  insert(int u,int v,int c,int w)    
26    {
27     add(u,v,c,w);
28     add(v,u,-c,0);
29    }
30       
31 bool spfa()
32    {
33      que[0]=0;
34      int h=1,t=0;
35       inq[0]=1;
36       for (int i=1;i<=T;i++) dis[i]=0x7fffffff;
37       dis[0]=0;
38       while (h!=t)
39          {
40             int now=que[t++];
41             //que.pop();
42             for (int i=head[now];i;i=e[i].next)
43                    if (e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
44                       {
45                          dis[e[i].to]=dis[now]+e[i].c;
46                          from[e[i].to]=i;
47                          if (!inq[e[i].to])
48                              inq[e[i].to]=1,que[h++]=e[i].to;
49                       }
50             inq[now]=0;           
51          }
52    if (dis[T]==0x7fffffff) return 0;
53        else return 1;        
54    }
55       
56 void mcf()
57    {
58      int x=0x7fffffff,a,b,y;
59      for (int i=from[T];i;i=from[e[i].from])
60        {
61          x=min(e[i].v,x);
62          if(e[i].from==0)
63             {y=e[i].to;a=(y-1)/tot+1;b=y%tot+1;}
64        }
65      for (int i=from[T];i;i=from[e[i].from])
66          {
67            e[i].v-=x; e[i^1].v+=x;  
68            ans+=e[i].c*x;
69          } 
70     for (int i=1;i<=n;i++)
71         insert((a-1)*tot+b,m*tot+i,b*t[i][a],1);        
72    }         
73       
74 int main()
75   {
76     scanf("%d%d",&n,&m);
77     for (int i=1;i<=n;i++)
78        scanf("%d",&c[i]),tot+=c[i];
79     for(int i=1;i<=n;i++)
80         for(int j=1;j<=m;j++)
81             scanf("%d",&t[i][j]);   
82     for (int i=1;i<=m*tot;i++)
83        insert(0,i,0,1);
84     for (int i=1;i<=n;i++)
85        insert(i+m*tot,T,0,c[i]);
86     for (int i=1;i<=m;i++)
87        for (int j=1;j<=n;j++)
88           insert((i-1)*tot+1,m*tot+j,t[j][i],1);
89     while (spfa()) 
90     mcf();
91      printf("%d
",ans);         
92     return 0;
93 }