HDU 3026 Chinese Chess 二分匹配（TLE...）

本文主要是介绍HDU 3026 Chinese Chess 二分匹配（TLE...），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求有多少个点，满足不选这个点最大匹配减少，超时了，挖个坑， 以后实力够了在来填坑。。。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10010;
const int maxm = 10010;
bool vis[maxn];
int y[maxn];
int n, m;
vector<int> G[maxn];
int b[maxn];
int nowx, nowy, flag;
bool dfs(int u)
{
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(vis[v] || (flag && u == nowx && v == nowy))
continue;
vis[v] = true;
if(y[v] == -1 || dfs(y[v]))
{
y[v] = u;
return true;
}
}
return false;
}
int match()
{
int ans = 0;
memset(y, -1, sizeof(y));
for(int i = 0; i < n; i++)
{
memset(vis, false, sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
int cas = 1;
int T;
int k;
//scanf("%d", &T);
while(scanf("%d %d %d", &n, &m, &k) != EOF)
{
flag = 0;
for(int i  = 0; i <= n; i++)
G[i].clear();
memset(b, 0, sizeof(b));
while(k--)
{
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
G[u].push_back(v);
}
int ans = match();
int sum = 0;
memset(b, 0, sizeof(b));
for(int j = 0; j < m; j++)
if(y[j] != -1)
b[y[j]] = 1;
flag = 1;
for(int i = 0; i < m; i++)
{
if(y[i] == -1)
continue;
int temp = y[i];
y[i] = -1;
nowx = temp;
nowy = i;
b[temp] = 0;
int flag2 = 0;
for(int j = 0; j < n; j++)
{
memset(vis, 0, sizeof(vis));
if(!b[j] && dfs(j))
flag2 = 1;
if(flag2)
break;
}
if(!flag2)
{
sum++;
y[i] = temp;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", cas++, sum, ans);
}
return 0;
}

这篇关于HDU 3026 Chinese Chess 二分匹配（TLE...）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---