nyoj 237
游戲高手的煩惱
時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：5 描述有一位傳說級(jí)游戲高手，在閑暇時(shí)間里玩起了一個(gè)小游戲，游戲中，一個(gè)n*n的方塊形區(qū)域里有許多敵人，玩家可以使用炸彈炸掉某一行或者某一列的所有敵人。他是種玩什么游戲都想玩得很優(yōu)秀的人，所以，他決定，使用盡可能少的炸彈炸掉所有的敵人。
現(xiàn)在給你一個(gè)游戲的狀態(tài)，請(qǐng)你幫助他判斷最少需要多少個(gè)炸彈才能炸掉所有的敵人吧。
比如說，下圖中X表示敵人
X . X?
. X .?
. X .?
則，他只需要炸掉第1行與第2列就能炸掉所有的敵人，所以只需要兩顆炸彈就可以了。
輸入
每組測(cè)試數(shù)據(jù)的第一行有兩個(gè)整數(shù)n,K，其中n表示游戲方形區(qū)域的大小。(n<=500,K<=10 000)
隨后的K行，每行有兩個(gè)整數(shù)i,j表示第i行，第j列有一個(gè)敵人(行和列都從1開始編號(hào)）。(1<=i,j<=n)
2
解題思路：這道題目難在建圖，很難將它與二分圖聯(lián)系在一起。。實(shí)際上只要是橫坐標(biāo)相同或者縱坐標(biāo)相同，只需要一個(gè)炸彈就能搞定，如果敏感的話就能夠分析它要求的是二分圖的最小點(diǎn)覆蓋。。分成兩個(gè)集合X,Y（所有敵人的橫坐標(biāo)在X，縱坐標(biāo)在Y），假定x0分別與y1，y2，y3連接了一條邊，那么可以清楚的知道，(x0,y1),(x0,y2),(x0,y3)這三個(gè)敵人只需要一個(gè)炸彈即可。。。換句話說，我只要找到一個(gè)點(diǎn)就可以把與之相關(guān)聯(lián)的邊都覆蓋掉。。。圖論的題目最困難的還是在建圖
AC:
#include <stdio.h> #include <string.h>const int N = 505; const int M = 10005;struct Vertex {int head; }V[N];struct Edge {int v,next; }E[M];int top,match[N];bool used[N];void Init() {top = 0;memset(V,-1,sizeof(V));memset(match,0,sizeof(match)); }void Add_Edge(int u,int v) {E[top].v = v;E[top].next = V[u].head;V[u].head = top++; }bool dfs(int u) {for(int i=V[u].head;~i;i=E[i].next){int v = E[i].v;if(!used[v]){used[v] = true;if(!match[v] || dfs(match[v])){match[v] = u;return true;}}}return false; }int maxMatch(int n) {int ans = 0;for(int i=1;i<=n;i++){memset(used,false,sizeof(used));if(dfs(i))++ans;}return ans; }int main() {int z,n,m,num;scanf("%d",&z);while(z--){Init();scanf("%d%d",&n,&m);while(m--){int i,j;scanf("%d%d",&i,&j);Add_Edge(i,j);}printf("%d\n",maxMatch(n));}return 0; }
總結(jié)
- 上一篇： 【JEECG Dubbo专题】Dubb
- 下一篇： Activiti 工作流会签开发设计思路