LA2238 二分图最佳完美匹配

分析：

先看一个内存区域的情况。假设在这个内存区域按顺序执行的k个程序的运行时间分别为t1,t2,t3,t4,...,tk, 那么第i个程序的回转时间为r = t1+t2+...+ti,所有程序的回转时间之和等于 r=kt1+(k-1)t2 + ... +2tk-1 + tk。

换句话，如果程序i是内存区域j的倒数第p个执行程序，则它对于总回转时间的“贡献值”为pTi,j, 其中Ti,j 为程序i在内存区域j中的运行时间。

构造二分图G,X结点为n个程序，Y结点为n*m个“位置”，其中位置（j,p）表示第j个内存区域的倒数第p个执行程序。每个X结点i和Y结点（j,p）连有一条权值为pTij的边，然后求最小权匹配即可。

注意，并不是每个匹配都对应一个合法方案。（比如，一个区域不能只有倒数第一个程序而没有倒数第二个程序），但最佳匹配一定对应一个合法方案。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 500+5;
const int INF = 1e9;
int mn; //左右顶点个数
int W[maxn][maxn]; //权值
int Lx[maxn],Ly[maxn]; //顶标
int left[maxn]; //left[i]为右边第i个点的匹配点编号，-1表示不存在
bool S[maxn],T[maxn];  //S[i]和T[i]为左/右第i个点是否已经标记
vector<int>G[maxn]; //邻接表

int MAX(int x, int y){return x>y?x:y;}
int MIN(int x, int y){return x<y?x:y;}

const int maxp = 50+5; //程序最大数目
const int maxr = 10+5; //区域最大数目
int n,m;  //程序数目和区域数目
int runtime[maxp][maxr]; //程序p在区域r中运行的时间
int sz[maxr];
int kase = 0;

void init(){
    mn = n*m;
    for (int i=0; i<mn; i++) G[i].clear();
    memset(W,0,sizeof(W));
}

void addEdge(int u, int v, int w){
    G[u].push_back(v);
    W[u][v] = w;
}

bool match(int u){
    S[u] = 1;
    for (int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if (Lx[u]+Ly[v]==W[u][v] && !T[v]) {
            T[v] = 1;
            if (left[v]==-1 || match(left[v])){
                left[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

void update(){
   int a = INF;
   for (int u=0; u<mn; u++) if (S[u])
     for (int i=0; i<G[u].size(); i++) {
         int v = G[u][i];
         if (!T[v]) a = MIN(a,Lx[u]+Ly[v]-W[u][v]);
     }

   for (int i=0; i<mn; i++) {
       if (S[i]) Lx[i] -= a;
       if (T[i]) Ly[i] += a;
   }
}

void solve(){
     for (int i=0; i<mn; i++) {
         Lx[i] = *max_element(W[i],W[i]+mn);
         left[i] = -1;
         Ly[i] = 0;
     }
     for (int u=0; u<mn; u++){
        for (;;){
            for (int i=0; i<mn; i++) S[i] = T[i] = 0;
            if (match(u)) break; else update();
        }
     }
}

void Print(){
    int start[maxp], region_num[maxp], tot = 0; //起始时刻，分配到的区域编号，总回转时间
    for (int region = 0; region <m; region++){
        vector<int> programs;
        for (int pos = 0; pos<n; pos++) {
            int r = n*region + pos;
            int l = left[r];
            if (l>=n) break; //匹配到虚拟结点，说明本region已经没有更多程序了
            programs.push_back(l);
            region_num[l] = region;
            tot -= W[l][r];
        }
        reverse(programs.begin(),programs.end());
        int time = 0;
        for (int i=0; i<programs.size(); i++) {
            start[programs[i]] = time;
            time += runtime[programs[i]][region];
        }
    }

    printf("Case %d\n",++kase);
    printf("Average turnaround time = %.2lf\n",(double)tot/n);
    for (int p = 0; p<n; p++) printf("Program %d runs in region %d from %d to %d\n",p+1,region_num[p]+1,start[p],start[p]+runtime[p][region_num[p]]);
    printf("\n");
}

int main(){
    int s[10], t[10], k;
    while (scanf("%d %d",&m,&n) && n+m){
        init();
        for (int i=0; i<m; i++) scanf("%d",&sz[i]);
        for (int i=0; i<n; i++){
            scanf("%d",&k);
            for (int j =0; j<k; j++) scanf("%d%d",&s[j],&t[j]);

            for (int region = 0; region<m; region++){
                int &time = runtime[i][region];
                time = INF;
                if (sz[region]<s[0]) continue;

                for (int j=0; j<k; j++) {
                    if (j==k-1 || sz[region]<s[j+1]) {
                        time = t[j];
                        break;
                    }
                }

                for (int pos = 0; pos<n; pos++) addEdge(i,region*n+pos,-(pos+1)*time);
            }
        }

        //补充其他边
        for (int i=n; i< mn; i++) {
            for (int j=0; j<mn; j++) addEdge(i,j,1);
        }

        solve();
        Print();
    }
    return 0;
}