zoj2182.cpp

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

#include <algorithm>
#include <ctype.h>
#include <vector>
using namespace std;
const int MAXN = 110;

int n, m, ans;
bool g[MAXN][MAXN];
char s[10000];
vector<int> gg[MAXN];

bool init(){
    if (EOF == scanf("%d %d", &n, &m)) return false;
    memset(g, 0, sizeof(g));
    int u, v;
    for (int i = 0; i < m; i++){ 
        scanf(" (%d,%d)", &u, &v);
        g[u][v] = g[v][u] = true;
    }
    return true;
}

int N, src, dst, c[MAXN][MAXN];
int f[MAXN][MAXN], pnt[MAXN], open[MAXN], d[MAXN], mk[MAXN];

int maxflow(int n = N, int s = src, int t = dst){
	int cur, tail, i, j, u, v, flow=0;  memset(f,0,sizeof(f));
	do{ memset(mk,0,sizeof(mk)); memset(d,0,sizeof(d));
		open[0]=s; mk[s]=1; d[s]=0x3fffffff;
		for(pnt[s]=cur=tail=0;cur<=tail&&!mk[t];cur++)
			for(u=open[cur],i=0;i<gg[u].size();i++){
                v = gg[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];
		if (flow >= ans) return flow;
		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 build(){
    N = 2 * n + 1;
    memset(c, 0, sizeof(c));
    int u, v;
    for (int i = 0; i < n; i++) gg[i].clear();
    for (int i = 0; i < n; i++) {
        c[i*2][i*2+1] = 1;
        gg[i*2].push_back(i*2+1);
        gg[i*2+1].push_back(i*2);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (g[i][j]){
            u = 2 * i + 1;  v = 2 * j;
            gg[u].push_back(v);
            gg[v].push_back(u);
            c[u][v] = 0x3fffffff;
        }
}   

void solve(){
    ans = n;
    build();
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++){
            src = 2 * i + 1;  dst = 2 * j;
            int tmp = maxflow();   
            ans <?= tmp;
        }
    printf("%d\n", ans);
}

int main(){
    while (init()) solve();
    return 0;   
}