二分匹配
染色法判断二分图
#include <bits/stdc++.h>
using namespace std;
const int MAXN =
300;
int n, m;
vector<int> G[MAXN];
int col[MAXN];
bool dfs1(
int v,
int c)
{
col[v] = c;
for(
int i=
0; i<(
int)G[v].size(); ++i)
{
if(col[G[v][i]] == c)
return false;
if(col[G[v][i]] ==
0 && !dfs1(G[v][i], -c))
return false;
}
return true;
}
bool check()
{
memset(col,
0,
sizeof(col));
for(
int i=
0; i<n; ++i)
{
if(col[i]==
0 && !dfs1(i,
1))
return false;
}
return true;
}
匈牙利算法(DFS)
#include <bits/stdc++.h>
using namespace std;
const int MAXV =
100;
vector<int> G[MAXV];
int numl, numr, num;
int match[MAXV];
bool vist[MAXV];
bool dfs(
int u)
{
for(
int i=
0; i<(
int)G[u].size(); ++i)
{
int v = G[u][i];
if(!vist[v])
{
vist[v] =
1;
if(match[v] == -
1 || dfs(match[v]))
{
match[v] = u;
match[u] = v;
return true;
}
}
}
return false;
}
int Hungarian()
{
int ans =
0;
memset(match, -
1,
sizeof(match));
for(
int u=
0; u<numl; ++u)
{
if(match[u] == -
1)
{
memset(vist,
0,
sizeof(vist));
if(dfs(u)) ++ans;
}
}
return ans;
}
void add_edge(
int u,
int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void init()
{
for(
int i=
0; i<MAXV; ++i) G[i].clear();
}
int n;
char s[
5][
5];
int r[
5][
5], c[
5][
5];
int main()
{
while(
cin >> n && n)
{
init();
for(
int i=
0; i<n; ++i)
cin >> s[i];
int now =
0;
for(
int i=
0; i<n; ++i)
{
for(
int j=
0; j<n; ++j)
if(s[i][j]==
'.') r[i][j] = now;
else if(s[i][j+
1]==
'.') now++;
now++;
}
for(
int j=
0; j<n; ++j)
{
for(
int i=
0; i<n; ++i)
if(s[i][j]==
'.') c[i][j] = now;
else if(s[i+
1][j]==
'.') now++;
now++;
}
numl = now;
for(
int i=
0; i<n; ++i)
for(
int j=
0; j<n; ++j)
if(s[i][j] ==
'.')
add_edge(c[i][j], r[i][j]);
cout << Hungarian() << endl;
}
return 0;
}
矩阵
#include <bits/stdc++.h>
using namespace std;
const int MAXN =
400;
int G[MAXN][MAXN], match[MAXN];
bool vist[MAXN];
int numl, numr;
bool dfs(
int u)
{
for(
int v=
1; v<=numr; ++v)
{
if(G[u][v]!=
0 && !vist[v])
{
vist[v] =
1;
if(match[v]==-
1 || dfs(match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
int Hungarian()
{
int ans =
0;
memset(match, -
1,
sizeof(match));
for(
int i=
1; i<=numl; ++i)
{
memset(vist,
0,
sizeof(vist));
if(dfs(i)) ++ans;
}
return ans;
}
HC
#include <bits/stdc++.h>
using namespace std;
const int MAXN =
3030;
const int INF =
0x3f3f3f3f;
vector<int>G[MAXN];
int uN;
int Mx[MAXN],My[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP()
{
queue<int>Q;
dis = INF;
memset(dx,-
1,
sizeof(dx));
memset(dy,-
1,
sizeof(dy));
for(
int i =
0 ; i < uN; i++)
if(Mx[i] == -
1)
{
Q.push(i);
dx[i] =
0;
}
while(!Q.empty())
{
int u = Q.front();
Q.pop();
if(dx[u] > dis)
break;
int sz = G[u].size();
for(
int i =
0;i < sz;i++)
{
int v = G[u][i];
if(dy[v] == -
1)
{
dy[v] = dx[u] +
1;
if(My[v] == -
1)dis = dy[v];
else
{
dx[My[v]] = dy[v] +
1;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
bool DFS(
int u)
{
int sz = G[u].size();
for(
int i =
0;i < sz;i++)
{
int v = G[u][i];
if(!used[v] && dy[v] == dx[u] +
1)
{
used[v] =
true;
if(My[v] != -
1 && dy[v] == dis)
continue;
if(My[v] == -
1 || DFS(My[v]))
{
My[v] = u;
Mx[u] = v;
return true;
}
}
}
return false;
}
int MaxMatch()
{
int res =
0;
memset(Mx,-
1,
sizeof(Mx));
memset(My,-
1,
sizeof(My));
while(SearchP())
{
memset(used,
false,
sizeof(used));
for(
int i =
0;i < uN;i++)
if(Mx[i] == -
1 && DFS(i))
res++;
}
return res;
}
struct P
{
int x, y, v;
};
P p1[MAXN], p2[MAXN];
int cal(
const P & a,
const P &b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int main()
{
int T, t, n, m;
cin >> T;
for(
int cas=
1; cas<=T; ++cas)
{
scanf(
"%d%d", &t, &n);
for(
int i=
0; i<n; ++i)
scanf(
"%d%d%d", &p1[i].x, &p1[i].y, &p1[i].v);
scanf(
"%d", &m);
for(
int i=
0; i<m; ++i)
scanf(
"%d%d", &p2[i].x, &p2[i].y);
for(
int i=
0; i<n; ++i) G[i].clear();
uN = n;
for(
int i=
0; i<n; ++i)
for(
int j=
0; j<m; ++j)
if(cal(p1[i], p2[j]) <= p1[i].v*p1[i].v*t*t) G[i].push_back(j);
printf(
"Scenario #%d:\n%d\n\n", cas, MaxMatch());
}
return 0;
}
