二分图的最大匹配。
每一个$0$与$1$配对，只建立满足时差大于等于$a$或者小于等于$b$的边，如果二分图最大匹配等于$n/2$，那么有解，遍历每一条边输出答案，否则无解。
#include #include<set> #include #include #include #include<string> #include #include #include #include #include #include using namespace std; #define ms(x,y) memset(x,y,sizeof(x)) #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define loop(i,j,k) for (int i=j;i!=-1;i=k[i]) #define inone(x) scanf("%d",&x) #define intwo(x,y) scanf("%d%d",&x,&y) #define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z) #define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p) #define lson x<<1,l,mid #define rson x<<1|1,mid+1,r #define mp(i,j) make_pair(i,j) #define ft first #define sd second typedef long long LL; typedef pair<int, int> pii; const int low(int x) { return x&-x; } const int INF = 0x7FFFFFFF; const int mod = 1e9 + 7; const int N = 1e6 + 10; const int M = 1e4 + 1; const double eps = 1e-10; int a,b,n; int T[1010],f[1010]; const int maxn = 1010 + 10; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){} }; vectoredges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int s, t; void init() { for (int i = 0; i ) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int w = edges.size(); G[from].push_back(w - 2); G[to].push_back(w - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i) { Edge e = edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i) { Edge e = edges[G[x][i]]; if (d[x]+1 == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow; } int dinic(int s, int t) { int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } int main() { while(~scanf("%d%d",&a,&b)) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&T[i],&f[i]); init(); for(int i=1;i<=n;i++) { if(f[i]==1) continue; for(int j=i+1;j<=n;j++) { if(f[j]==0) continue; if(T[j]-T[i]>=a||T[j]-T[i]<=b) { AddEdge(i,j,1); } } } s=0,t=n+1; for(int i=1;i<=n;i++) { if(f[i]==0) AddEdge(s,i,1); else AddEdge(i,t,1); } int M = dinic(s,t); if(M2) { printf("Liar\n"); } else { printf("No reason\n"); for(int i=0;i) { if(edges[i].flow!=1) continue; if(edges[i].from!=s&&edges[i].to!=t) printf("%d %d\n",T[edges[i].from],T[edges[i].to]); } } } return 0; }
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号