本文共 4141 字,大约阅读时间需要 13 分钟。
#include#include using namespace std;const int MAXN = 1000; int uN, vN; // u, v数目,要初始化!!! bool g[MAXN][MAXN]; // g[i][j] 表示xi与yj相连 int xM[MAXN], yM[MAXN]; // xM[i]:cow i已经被分配到stall xM[i]; stall j 已经被分配给cow yM[j]bool chk[MAXN]; // 辅助量检查某轮y[v]是否被check bool SearchPath(int u){ int v; for(v = 0; v < vN; v++) if(g[u][v] && !chk[v]) { chk[v] = true; //从u--->v //改为 //u<-----v if(yM[v] == -1 || SearchPath(yM[v]))//如果已经存在于v相连的u的匹配 { yM[v] = u; xM[u] = v; return true ; } } return false ; } int MaxMatch(){ int u, ret = 0 ; memset(xM, -1, sizeof (xM)); memset(yM, -1, sizeof (yM)); for(u = 0; u < uN; u++) if(xM[u] == -1){ memset(chk, false, sizeof (chk)); if(SearchPath(u)) ret++; } return ret; } int main(){ int i,j,t,N,M,m,res; //N:cows,M:stalls while(cin>>N>>M) { uN=N; vN=M; memset(g,0,sizeof(g)); for(i=0;i >t; for(j=0;j >m; g[i][m-1]=1; } } cout< <
void init_d(){ re(i, n) E[i].pre = E[i].next = i; m = n;}void add_edge(int a, int b, int len){ E[m].a = a; E[m].b = b; E[m].len = len; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;}inline int dist(int x, int y, int x0, int y0){ return abs(x - x0) + abs(y - y0);}bool dfs(int x){ int y, x0; fx[x] = _FLAG; for (int p=E[x].next; p != x; p=E[p].next) { y = E[p].b; if (lx[x] + ly[y] > E[p].len) { if (lx[x] + ly[y] - E[p].len < slk[y]) slk[y] = lx[x] + ly[y] - E[p].len; } else if (fy[y] != _FLAG) { fy[y] = _FLAG; x0 = z[y]; if (x0 == -1 || dfs(x0)) {z[y] = x; return 1;} } } return 0;}void solve(){ re(i, n) { lx[i] = -INF; for (int p=E[i].next; p != i; p=E[p].next) if (E[p].len > lx[i]) lx[i] = E[p].len; } re(i, n0) {ly[i] = 0; z[i] = -1;} int d; re(i, n) { re(j, n0) slk[i] = INF; _FLAG++; while (!dfs(i)) { d = INF; re(j, n0) if (fy[j] != _FLAG && slk[j] < d) d = slk[j]; re(j, n) if (fx[j] == _FLAG) lx[j] -= d; re(j, n0) {slk[j] = INF; if (fy[j] == _FLAG) ly[j] += d;} _FLAG++; } } res = 0; re(i, n) res += lx[i]; re(i, n0) res += ly[i];}
转载地址:http://ibeti.baihongyu.com/