?? 2199484_wa.c
字號:
# include <stdio.h>
# include <string.h>
int n, d, k, no;
char plug[502][30];
char dev[502][30];
int g[502][502];
int b[502], link[502];
char tmp1[30], tmp2[30], tmp[30], adp[502][30];
void warshall(int map[][502])
{
int i, j, m;
for(i = 0; i < no; i++)
{
for(j = 0; j < no; j++)
if(map[j][i])
for(m = 0; m < no; m++)
map[j][m] += map[i][m];
}
}
void insert(int i,int j)
{
int m, p;
for(m = 1; m <= n; m++)
if(strcmp(plug[m],adp[j])==0)
for(p = 1; p <= d; p++)
if(strcmp(adp[i],dev[p])==0)
g[m][p] = 1;
}
int find(int a)
{
int i;
for(i = 1; i <= d; i++)
{
if(g[a][i]&&!b[i])
{
b[i] = 1;
if(!link[i]||find(link[i]))
{
link[i] = 1;
return 1;
}
}
}
return 0;
}
void solve(int map[][502])
{
int i, j, ans;
ans = 0;
for(i = 0; i < no; i++)
for(j = 0; j < no; j++)
if(map[i][j])
insert(i,j);
for(i = 1; i <= n; i++)
{
memset(b,0,sizeof(b));
if(find(i))
ans++;
}
printf("%d\n",d-ans);
}
void input()
{
int f1, f2;
int i, j, m;
int map[502][502];
scanf("%d",&n);
no = 0;
memset(map,0,sizeof(map));
memset(g,0,sizeof(g));
for(i = 1; i <= n; i++)
scanf("%s",plug[i]);
scanf("%d",&d);
for(i = 1; i <= d; i++)
{
scanf("%s%s",tmp,dev[i]);
for(j = n; j > 0; j--)
if(strcmp(dev[i],plug[j])==0)
g[j][i] = 1;
}
scanf("%d",&k);
for(i = 1; i <= k; i++)
{
scanf("%s%s",tmp1,tmp2);
if(strcmp(tmp2,tmp1)==0)
continue;
f1 = f2 = 0;
for(j = 0; j <no; j++)
if(strcmp(tmp1,adp[j])==0)
{
f1 = 1;
break;
}
for(m = 0; m < no; m++)
if(strcmp(tmp2,adp[m])==0)
{
f2 = 1;
break;
}
if(f1)
{
if(f2)
map[j][m] = 1;
else
{
strcpy(adp[no],tmp2);
map[j][no++] = 1;
}
}
else
{
if(f2)
{
strcpy(adp[no],tmp1);
map[no++][m] = 1;
}
else
{
strcpy(adp[no++],tmp1);
strcpy(adp[no++],tmp2);
map[no-2][no-1] =1;
}
}
}
warshall(map);
solve(map);
}
int main()
{
input();
return 1;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -