### Andrew Stankevich’s Contest #3解题报告 » ZOJ2362

ZOJ2362.java

```// TAG : Hungary
// TAG : Bipartite

import java.util.*;

class Matching {
public static int hungary(int nu, int nv, ArrayList<ArrayList<Integer> > e, int[] mu, int[] mv) {
if (mu == null) {
mu = new int[nu];
}
Arrays.fill(mu, -1);
if (mv == null) {
mv = new int[nv];
}
Arrays.fill(mv, -1);
int[] q = new int[nu];
int[] p = new int[nv];
int ret = 0;
for (int i = 0; i < nu; ++i) {
Arrays.fill(p, -1);
q[0] = i;
int t = 1;
BFS:
for (int s = 0; s < t; ++s) {
int k = q[s];
for (int j : e.get(k)) {
if (p[j] == -1) {
if (mv[j] == -1) {
int x = k, y = j, z;
while(true) {
z = mu[x];
mu[x] = y;
mv[y] = x;
if (z == -1) {
break;
} else {
x = p[z];
y = z;
}
}
++ret;
break BFS;
} else {
q[t++] = mv[j];
p[j] = k;
}
}
}
}
}
return ret;
}
}

public class Main {
static int ch;

public static int nextInt() {
int ret = 0;
try {
continue;
}
do {
ret *= 10;
ret += Character.digit(ch, 10);
} catch (java.io.IOException e) {
}
return ret;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int re = nextInt();
for (int ri = 1; ri <= re; ++ri) {
if (ri > 1) {
System.out.println();
}
int n = nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = nextInt();
a[i] = a[i] * 1024 + i;
}
Arrays.sort(a);
int[] b = new int[n];
for (int i = 0; i < n; ++i) {
b[a[n - 1 - i] & 1023] = i;
}
ArrayList<ArrayList<Integer> > e = new ArrayList<ArrayList<Integer> >(n);
for (int i = 0; i < n; ++i) {
}
for (int i = 0; i < n; ++i) {
int k = nextInt();
ArrayList<Integer> ee = new ArrayList<Integer>(k);
for (int j = 0; j < k; ++j) {
}
e.set(b[i], ee);
}
int[] m = new int[n];
System.err.println(Matching.hungary(n, n, e, m, new int[n]));
for (int i = 0; i < n; ++i) {
if (i > 0) {
System.out.print(' ');
}
System.out.print(m[b[i]] + 1);
}
System.out.println();
}
}
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1791348 	2009-03-16 23:10:22 	Accepted 	2362 	Java 	0 	1812 	watashi@Zodiac
```