- Miku_Nobody
- 2016-12-30 01:16:25 @
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 220;
const int INF = 111111111;
using namespace std;
struct EdmoundsKarp{
struct Edge{
int from, to, cap, flow;
Edge(int a, int b, int c, int d) :from(a), to(b), cap(c), flow(d) {}
Edge(){}
};
int n, m;
vector<Edge> edges;//边数两倍
vector<int> G[maxn];//G[i][j]表示i的第j条边在edges中的编号
int a[maxn];//增量
int p[maxn];
void init(int n){
this->n = n;
for(int i = 0;i<n;i+=1) 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));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int MaxFlow(int s, int t){
int flow = 0;
for (;;){
Mem(a, 0);
queue<int> Q;
Q.push(s);
a[s] = INF;
while (!Q.empty()){//实际上每次BFS目的只是找到一条增广路
int x = Q.front(); Q.pop();
for (int i = 0; i<G[x].size(); i += 1){
Edge & e = edges[G[x][i]];
if (!a[e.to] && e.cap > e.flow){
p[e.to] = G[x][i];
a[e.to] = min(a[x], e.cap - e.flow);
Q.push(e.to);
}
}
if (a[t]) break;//如果到汇点的增量不为0证明增广路径已经找到
}
if (!a[t]) break;//如果枚举全部的边,汇点的增量也只能是0,证明已经是最大流
for (int u = t; u != s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
};
bool Judge(int A, int B) {
int* pMax = (A > B) ? &A : &B;
while (*pMax > 0) {
int nLast_A = A & 1;
int nLast_B = B & 1;
if (nLast_A == nLast_B) return false;
if (A > 0) A >>= 1;
if (B > 0) B >>= 1;
}
return true;
}
int main(){
EdmoundsKarp D;
int n, m;
vector<int> A, B;
scanf("%d %d", &n, &m);
if (n < m) swap(n, m);
A = vector<int>(n); B = vector<int>(m);
for (int i = 0; i < n; i += 1) scanf("%d", &A[i]);
for (int i = 0; i < m; i += 1)scanf("%d", &B[i]);
int S = 28, T = 29;
D.init(30);
for (int i = 0; i < n; i += 1)
for (int j = 0; j < m; j += 1){
if (Judge(A[i],B[j]))
D.AddEdge(A[i], B[j], 1);
}
for (int i = 0; i < n; i += 1) D.AddEdge(S, A[i], 1);
for (int i = 0; i < m; i += 1) D.AddEdge(B[i], T, 1);
int ans = D.MaxFlow(S, T);
if(ans) printf("%d\n", ans);
else printf("I want nobody nobody but you\n");
Sy;
return 0;
}
0 条评论
目前还没有评论...