php网站上线/外贸快车

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2389

 

不能用匈牙利，会TEL的，用Hopcroft-Karp

 

Hopcroft-Karp课件

以前是寻找一个增广路，这个是寻找所有的增广路，并且使用BFS进行分层

 

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;#define N 3100
#define INF 0xfffffffstruct node
{int x, y, s;
} x[N], y[N];struct Node
{int v, next;
} a[N*N];int  head[N], cnt, n, m;
bool used[N];
int  Mx[N], My[N], depth; ///记录的所匹配的端点，0表示未匹配
int  dx[N], dy[N]; ///BFS分层时，记录点所在的层，-1表示不在分层void Init()
{cnt = 0;memset(head, -1, sizeof(head));
}void Add(int u, int v)
{a[cnt].v = v;a[cnt].next = head[u];head[u] = cnt++;
}bool BFS()///如果发现y这边有增广路，返回1，否则返回0
{queue<int> Q; depth = INF;memset(dx, -1, sizeof(dx));memset(dy, -1, sizeof(dy));for(int i=1; i<=n; i++){if( Mx[i] == false ){dx[i] = 0;Q.push(i);}}while(Q.size()){int u = Q.front(); Q.pop();if(dx[u] > depth) break;///已经找到了增广路，不必寻找下层for(int j=head[u]; j!=-1; j=a[j].next){int v = a[j].v;if( dy[v] == -1 ){dy[v] = dx[u] + 1;if(My[v] == false)depth = dy[v];else{dx[ My[v] ] = dy[v] + 1;Q.push( My[v] );}}}}if( depth == INF )return false;return true;
}
bool Find(int i)
{for(int j=head[i]; j!=-1; j=a[j].next){int v = a[j].v;if( !used[v] && dx[i] == dy[v]-1){used[v] = true;if( My[v] && dy[v] == depth )continue;///不会在下一层，因为还没有对下层进行增广if( !My[v] || Find( My[v] ) ){My[v] = i;Mx[i] = v;return true;}}}return false;
}int Karp()
{int ans = 0;memset(Mx, false, sizeof(Mx));memset(My, false, sizeof(My));while( BFS() == true ){///如果还存在增广路memset(used, false, sizeof(used));for(int i=1; i<=n; i++){if( !Mx[i] && Find(i) == true )ans++;}}return ans;
}int main()
{int t, iCase=1;scanf("%d", &t);while(t--){int time, i, j;scanf("%d%d", &time, &n);Init();for(i=1; i<=n; i++){scanf("%d%d%d", &x[i].x, &x[i].y, &x[i].s);x[i].s = x[i].s*x[i].s*time*time;}scanf("%d", &m);for(i=1; i<=m; i++){scanf("%d%d", &y[i].x, &y[i].y);for(j=1; j<=n; j++){int d = (y[i].x-x[j].x)*(y[i].x-x[j].x) + (y[i].y-x[j].y)*(y[i].y-x[j].y);if( d <= x[j].s )Add(j, i);}}int ans = Karp();printf("Scenario #%d:\n%d\n\n", iCase++, ans);}return 0;
}