zoj2399.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

const int MAXN = 1550;
const int INF = 0x3fffffff;
int n, m;
int N, src, dst;
char s[10000], ts[1000];
vector<int> g[MAXN];
int c[MAXN][MAXN], f[MAXN][MAXN], d[MAXN];
int pnt[MAXN], open[MAXN], mk[MAXN];
int flow;

int maxFlow(int n = N, int s = src, int t = dst){
	int cur, tail, i, u, v;
	do{ memset(mk,0,sizeof(mk)); memset(d,0,sizeof(d));
		open[0] = s; mk[s] = 1; d[s] = INF;
		for(pnt[s]=cur=tail=0; cur<=tail&&!mk[t]; cur++)
			for(u=open[cur],i = 0; i < g[u].size(); i++){
                v = g[u][i];
                if(!mk[v]&&f[u][v]<c[u][v]){
				    mk[v]=1; open[++tail]=v; pnt[v]=u;
    				if(d[u]<c[u][v]-f[u][v])d[v]=d[u];
	   				else d[v]=c[u][v]-f[u][v];
			    }
            }
		if(!mk[t]) break; 
        flow+=d[t];
		for(u=t;u!=s;) {v=u;u=pnt[v];f[u][v]+=d[t]; f[v][u]=-f[u][v];}
	}while(d[t]>0); 
    return flow;
}


void init(){
    src = 0; dst = n + m + 1; N = n + m + 2;
    for (int i = 0; i < N; i++) g[i].clear();
    int x;
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++){
        gets(s);
        istringstream in(s);
        in >> ts;
        while (in >> x){ 
            c[i][n + x + 1] = 1;
            g[i].push_back(n + x + 1);
            g[n + x + 1].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++){
        c[src][i] = 1;
        g[src].push_back(i);
        g[i].push_back(src);
    }
    for (int i = n + 1; i <= n + m; i++){
        g[i].push_back(dst);
        g[dst].push_back(i);
    }
}

void solve(){
    flow=0;  memset(f,0,sizeof(f));
    for (int p = 1; p <= n; p++){
        for (int i = n + 1; i <= n + m; i++) c[i][dst] = p;           
        maxFlow();
        if (flow == n) {printf("%d\n", p); break;}
    }
}

int main(){
    while (scanf("%d %d", &n, &m) != EOF && n && m){
        gets(s);
        init();
        solve();   
    }    
    return 0;   
}