题面：
题意：酒吧里的人只会呆至多b分钟或者最少a分钟，，给出了酒吧里人的出入记录，判断有没有可能有不符合条件的人在酒吧呆过（在酒吧的时间大于b且小于a）
易知这题是个二分图匹配……然而数据量有1000，边数可能会到10^6。用匈牙利算法必然会TLE……于是鸡汁的队友想到了HK算法，可以在O(n^(1/2)*m)的时间求解。
然后……交上竟然T了……后来发现抄板抄错了……改过来之后WA……然后发现建图的时候手残连了不该连的边……坑了好多发终于过了orz//果然一个程序不该两个人一起写
学习了新的姿势，mark一下
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <queue>#include <ctime>using namespace std;const int MAXN = 1024;const int INF = 1 << 28;int bmap[MAXN][MAXN];int cx[MAXN];int cy[MAXN];int nx, ny;int dx[MAXN];int dy[MAXN];int dis;bool bmask[MAXN];//HKbool searchpath(){queue<int> Q;dis = INF;memset(dx, -1, sizeof(dx));memset(dy, -1, sizeof(dy));for (int i = 0; i<nx; i++){if (cx[i] == -1){Q.push(i);dx[i] = 0;}}while (!Q.empty()){int u = Q.front(); Q.pop();if (dx[u]>dis) break;for (int v = 0; v<ny; v++){if (bmap[u][v] && dy[v] == -1){dy[v] = dx[u] + 1;if (cy[v] == -1) dis = dy[v];else{dx[cy[v]] = dy[v] + 1;Q.push(cy[v]);}}}}return dis != INF;}int findpath(int u){for (int v = 0; v<ny; v++){if ((!bmask[v]) && bmap[u][v] && (dy[v] == (dx[u] + 1))){bmask[v] = 1;if (cy[v] != -1 && dy[v] == dis){continue;}if (cy[v] == -1 || findpath(cy[v])){cy[v] = u; cx[u] = v;return 1;}}}return 0;}int MaxMatch(){int res = 0;memset(cx, -1, sizeof(cx));memset(cy, -1, sizeof(cy));while (searchpath()){memset(bmask, 0, sizeof(bmask));for (int i = 0; i<nx; i++){if (cx[i] == -1){res += findpath(i);}}}return res;}int a, b, n;int ri[1024], ro[1024];int i_cnt = 0, o_cnt = 0;void input_and_build(){scanf("%d%d%d", &a, &b, &n);i_cnt = o_cnt = 0;for (int i = 1; i <= n; i++){int x, y;scanf("%d%d", &x, &y);if (y)ro[o_cnt++] = x;elseri[i_cnt++] = x;}for (int i = 0; i<i_cnt; i++){for (int j = 0; j<o_cnt; j++){//判断两个的时间差是不是合法if (((ro[j] – ri[i] >= 0) && (ro[j] – ri[i]) <= b) || (ro[j] – ri[i]) >= a)bmap[i][j] = 1;elsebmap[i][j] = 0;}}nx = i_cnt, ny = o_cnt;}int main(){input_and_build();//出/入个数不相等if ((i_cnt != n / 2) || (o_cnt != n / 2)){printf("Liar\n");return 0;}int ans = MaxMatch();if (ans == n / 2){printf("No reason\n");for (int i = 0; i < i_cnt; i++){int i1 = i, i2 = cx[i];printf("%d %d\n", ri[i1], ro[i2]);}}else{printf("Liar\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
也会让你心无旁骛，更会让你的心灵得到解脱和抚慰。
