void solve() {
for(int i = 1;i <= m; i++) scanf("%d", &mem[i]);
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n*m; j++)
w[i][j] = 1<<30;
for(int i = 1;i <= n; i++) {
int k;
scanf("%d", &k);
for(int j = 1;j <= k; j++) scanf("%d%d", &a[j], &t[j]);
a[k+1] = 1<<30;
for(int j = 1;j <= m; j++) {
for(int l = 1;l <= k; l++) if(mem[j] >= a[l] && mem[j] < a[l+1]) {
for(int ii = 1;ii <= n; ii++) {
w[i][(j-1)*n + ii] = ii*t[l];
}
}
}
}

KM();
}

int main() {
int cas = 1;
while(scanf("%d%d", &m, &n) != -1) {
solve();
printf("Case %d\n", cas++);
int ans = 0;
for(int i = 1;i <= n; i++) ans += lx[i];
for(int i = 1;i <= n*m; i++) ans += ly[i];
printf("Average turnaround time = %.2lf\n", (double)ans/n);

int from[55], to[55], in[55], sum; // from表示程序从什么时间开始，to表示结束时间，in表示在哪个内存区域里运行
for(int i = n*m;i >= 1; i--) {
if(i%n == 0) sum = 0;
if(match[i]) {
int tmp = w[match[i]][i];
from[match[i]] = sum;
int num = i%n;
if(i%n == 0) num = n;
to[match[i]] = sum = tmp/num + sum;
in[match[i]] = i/n + 1;
if(i%n == 0) in[match[i]]--;
}
}
for(int i = 1;i <= n; i++)
printf("Program %d runs in region %d from %d to %d\n", i, in[i], from[i], to[i]);
}
return 0;
}

UVa 11419 - SAM I AM

最小点覆盖， 求出最大匹配后，最后要找到最小的点覆盖集。最小的点覆盖集的寻找过程，先从右边的非匹配点出发找交错路，并把路径上的点都标记下，最后的点覆盖集就是左边的标记了的顶点加上右边未标记的匹配点。

[html]
/* **********************************************
Author : JayYe
Created Time: 2013-8-18 11:10:00
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 1000+10;

bool mp[maxn][maxn], vis[maxn];
int match[maxn], markl[maxn], markr[maxn], right[maxn], n, m;

// 求最大匹配数
bool dfs(int i) {
for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {
vis[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}
// 交错路寻找点覆盖集
void findmin(int i) {
markr[i] = 1;
for(int j = 1;j <= n; j++) if(mp[j][i] && !markl[j]) {
markl[j] = 1;
if(right[j]) {
findmin(right[j]);
}
}
}

int main() {
int k, i, j, x, y;
while(scanf("%d%d%d", &n, &m, &k) != -1 && n) {
for(i = 1;i <= n; i++)
for(j = 1;j <= m; j++)
mp[i][j] = 0;
while(k--) {
scanf("%d%d", &x, &y);
mp[x][y] = 1;
}
int ans = 0;
for(i = 1;i <= m; i++) match[i] = 0;
for(i = 1;i <= n; i++) {
for(j = 1;j <= m; j++) vis[j] = 0;
if(dfs(i)) ans++;
}
printf("%d", ans);
for(i = 1;i <= n; i++) markl[i] = markr[i] = right[i] = 0;
for(i = 1;i <= m; i++) if(match[i])
right[match[i]] = i;
for(i = 1;i <= m; i++) if(!match[i]){
findmin(i);
}
//左边标记过的匹配点
for(i = 1;i <= n; i++) if(markl[i]) printf(" r%d", i);
//右边未标记的匹配点
for(i = 1;i <= m; i++) if(match[i] && !markr[i])　 printf(" c%d", i); puts("");
}
return 0;
}

/* **********************************************
Author : JayYe
Created Time: 2013-8-18 11:10:00
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 1000+10;

bool mp[maxn][maxn], vis[maxn];
int match[maxn], markl[maxn], markr[maxn], right[maxn], n, m;