哎哎...自己刚刚一看到这个题目居然。。。。。什么都想不到...看了一下别人的解题报告说最大匹配...于是就自己开始构思啦...
对于这个棋盘，有K个可以放棋子的位置....那么
首先我们开始可以求出这K个位置能放的最多棋子
这个就是最大匹配啦..一开始自己老是想不到怎么匹配....可以这样想，用这个棋盘的行与列匹配，因为车要不相互攻击，那么意味着每行每列只能放一个，一旦一个棋子放在了x , y坐标位置，那么第x行第y列就不能再放其他棋子，放了的这个棋子，就把x和y连成一条边...如果还是不理解可以看如下图(结合题目案例1)
那么现在可以知道可以放置的最多棋子就是最大二分匹配，我们先存为flag
然后就是处理重要点：
其实也比较简单，我们对于这K个点，一一考虑，去掉这个点，再求一次最大匹配，如果这次的最大匹配小于flag，那么可以知道，这个点就是重要点（可以考虑案例1，无论去掉哪一个点之后的最大匹配任然是2）
附上代码：一开始还担心会超时，但是居然没有，哎哎，不过看着题目排名，好多人都是0k 0ms。。。却不见一个人拿出来分享一下题解.....只给人留下羡慕的份
// 46MS 244K
#include<stdio.h>
#include<string.h> #define MAX 101 int N,M,K;
int node[MAX*MAX][2];//点先存起来，后面去点判断要用到node[i][0]表示第i个点的x坐标。node[i][1]表示第i个点的y坐标
bool map[MAX][MAX];//棋盘
int link[MAX];
bool useif[MAX]; bool dfs(int t)
{
for(int i=1;i<=M;i++)
{
if(!useif[i] && map[t][i])
{
useif[i]=true;
if(link[i]==-1 || dfs(link[i]))
{
link[i]=t;return true;
}
}
}
return false;
} int match()
{
int sum=0;
memset(link,-1,sizeof(link));
for(int i=1;i<=N;i++)
{
memset(useif,false,sizeof(useif));
if(dfs(i))
sum++;
}
return sum;
} int main()
{
int i;
int cas=1;
while(~scanf("%d%d%d",&N,&M,&K))
{
memset(map,0,sizeof(map));
for(i=0;i<K;i++)
{
scanf("%d%d",&node[i][0],&node[i][1]);
map[node[i][0]][node[i][1]]=1;
}
int flag=match();//首先匹配一次
int ans=0;
for(i=0;i<K;i++)
{
map[node[i][0]][node[i][1]]=0;//除去这个点
int x=match();
if(x!=flag)
ans++;
map[node[i][0]][node[i][1]]=1;//要记得吧点补回来
}
printf("Board %d have %d important blanks for %d chessmen.\n",cas++,ans,flag);
}
return 0;
}
图画的很烂...不要喷
总结：对于这类问题的转换思维还是狠狠不够...要努力