hdu1526 二分匹配+ floyd

题意:

有N个插座,M个用电器,和K种转换器(每种有无限个),问最少多少个用电器无法充电.

思路 : 总的电器数减去电器和插座的最大匹配数

我有的是map去映射每一个串,根据转换器建边,然后跑一边floyd(为了确定连通性),

跑完后就再建一个图匹配用,这个图中当 i 插座和j用电器之间的距离不是inf时就可以连接ij;

然后一边匈牙利就ok了,提醒一点就是插座,用电器,转换器中的字符串有可能会出现不同的,

所以每一次建边的时候记得映射下就行了..

#include<stdio.h>

#include<string.h>

#include<string>

#include<map>

#define N 100 + 10

#define N_node 500 + 10

#define N_edge 10000 + 100

#define inf 100000000

using namespace std;

typedef struct

{

int to ,next;

}STAR;

typedef struct

{

char str[30];

}CHAZUO;

typedef struct

{

char str[30];

}YONGHU;

CHAZUO cz[N];

YONGHU yh[N];

STAR E[N_edge];

int list[N_node] ,tot;

int mk_gx[N_node] ,mk_dfs[N_node];

int mp[N_node][N_node];

map<string,int>hash_node;

void add(int a, int b)

{

E[++tot].to = b;

E[tot].next = list[a];

list[a] = tot;

}

int minn(int x ,int y)

{

return x < y ? x : y;

}

void floyd(int n)

{

for(int k = 1 ;k <= n ;k ++)

for(int i = 1 ;i <= n ;i ++)

for(int j = 1 ;j <= n ;j ++)

mp[i][j] = minn(mp[i][j] ,mp[i][k] + mp[k][j]);

}

int DFS_XYL(int s)

{

for(int k = list[s] ;k ;k = E[k].next)

{

int to = E[k].to;

if(mk_dfs[to]) continue;

mk_dfs[to] = 1;

if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))

{

mk_gx[to] = s;

return 1;

}

}

return 0;

}

int main ()

{

int n ,m ,k ,i ,j ,t ,nowt ,a ,b;

char str1[30] ,str2[30];

scanf("%d" ,&t);

while(t--)

{

hash_node.clear();

nowt = 0;

scanf("%d" ,&n);

for(i = 1 ;i <= n ;i ++)

{

scanf("%s" ,cz[i].str);

if(hash_node[cz[i].str] == 0)

hash_node[cz[i].str] = ++ nowt;

}

scanf("%d" ,&m);

for(i = 1 ;i <= m ;i ++)

scanf("%s%s",str1 ,yh[i].str);

for(i = 1 ;i <= 500 ;i ++)

for(j = 1 ;j <= 500 ;j ++)

if(i == j)mp[i][j] = 0;

else mp[i][j] = inf;

scanf("%d" ,&k);

for(i = 1 ;i <= k ;i ++)

{

scanf("%s%s" ,str1 ,str2);

if(hash_node[str1] == 0)

hash_node[str1] = ++ nowt;

if(hash_node[str2] == 0)

hash_node[str2] = ++ nowt;

a = hash_node[str1];

b = hash_node[str2];

mp[a][b] = 1;

}

floyd(nowt);

memset(list ,0 ,sizeof(list));

tot = 1;

for(i = 1 ;i <= m ;i ++)

for(int j = 1 ;j <= n ;j ++)

{

if(hash_node[yh[i].str] == 0)

hash_node[yh[i].str] = ++nowt;

if(mp[hash_node[yh[i].str]][hash_node[cz[j].str]] == inf)

continue;

add(i ,j);

}

int sum = 0;

memset(mk_gx ,255 ,sizeof(mk_gx));

for(i = 1 ;i <= nowt ;i ++)

{

memset(mk_dfs ,0 ,sizeof(mk_dfs));

sum += DFS_XYL(i);

}

printf("%d\n" ,m - sum);

if(t)puts("");

}

return 0;

}

巴特西

hdu1526 二分匹配+ floyd

最新文章

热门文章