Why Did the Cow Cross the Road III S

P3663 [USACO17FEB]Why Did the Cow Cross the Road III S

---

技术统计

难度：提高+/省选-

用时：半天

提交次数：5

unaccept 次数：3

ac次数：2

---

题意概括

已知一个n*n的网格图，k头牛，s条路。每条路将其相邻的两个格间隔（不能互通），询问有多少对牛不能相互到达。

数据范围

$1\le K\le 100,K\le N^{2}1≤K≤100,K≤N^{2}$1≤K≤100,K≤N21≤K≤100,K≤N2

---

---

解法一、DFS求联通块

知识点

1. DFS求联通块
2. 状态压缩（可有可无）

解法概括

枚举每一头牛，跑dfs，对其进行染色。

坑点

1. int 类型开不了10^8大小的数组，但bool型可以
2. dfs的边界
3. 统计答案时用类似于下图的方式进行统计
   

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,k,s,ans,cnt;
int g[111][111],dx[111],dy[111];
bool vis[111][111],inl[111][111][111][111];
void dfs(int x,int y,int fx,int fy)
{
    g[x][y]=g[fx][fy];
    vis[x][y]=1;
    if(inl[x][y][x+1][y]==0&&vis[x+1][y]==0)dfs(x+1,y,x,y);
    if(inl[x][y][x-1][y]==0&&vis[x-1][y]==0)dfs(x-1,y,x,y);
    if(inl[x][y][x][y+1]==0&&vis[x][y+1]==0)dfs(x,y+1,x,y);
    if(inl[x][y][x][y-1]==0&&vis[x][y-1]==0)dfs(x,y-1,x,y);
}
int main()
{
    //freopen("testdata.in","r",stdin);
    scanf("%d%d%d",&n,&k,&s);
    for(int i=1;i<=n;i++)vis[0][i]=vis[i][0]=vis[i][n+1]=vis[n+1][i]=1;
    for(int i=1;i<=s;i++)
    {
        int r1,r2,s1,s2;
        scanf("%d%d%d%d",&r1,&s1,&r2,&s2);
        inl[r1][s1][r2][s2]=1;
        inl[r2][s2][r1][s1]=1;
    }
    for(int i=1;i<=k;i++)scanf("%d%d",&dx[i],&dy[i]);
    
    for(int i=1;i<=k;i++)
    {
        if(vis[dx[i]][dy[i]]==0)
        {
            cnt++;
            g[0][0]=cnt;
            dfs(dx[i],dy[i],0,0);
        }
    }
    for(int i=1;i<=k;i++)
     for(int j=i+1;j<=k;j++)
     	if(g[dx[i]][dy[i]]!=g[dx[j]][dy[j]])ans++;
    printf("%d",ans);
    return 0;
}

---

解法二、并查集求联通块

知识点

1. 并查集

解法概括

然后并查集枚举每个点，在记录有几个集合，每个集合里有几个数。然后每个集合数量相乘和即为正解。

坑点

本解法我还没有打过码，但是是正确的。

---

---

类似题目

1. P1596 [USACO10OCT]湖计数Lake Counting
2. 古代象形符号（刘汝佳紫书P163）