踢以

給出多個點的坐標 有一種攻擊 可以把一次干掉同一列的 或者干掉同一行的 求最少的攻擊次數

肥西

由于問題是問選取最少的行和列干掉所有的隕石 可以把輸入的r和c看成r和c之間有一條連邊因為要實現干就干掉一行的也就是說 在同一行的是連到一個點上的
比如1 3 ，1 2 那么1 就有兩條邊 分別連到2，3
比如再來看 2 2 ，3 2 同一列 那么在二分圖最大匹配中 也就是只會選擇一個 所以用二分圖的最大匹配就可以表示出題目所要求的最小攻擊次數
那么就相當于把所有的點都轉化成了邊 問題就變成了求最小覆蓋集的個數
也就是最大匹配數
那么從第一個點開始不斷的找增廣路 不斷更新匹配數就好了

CoDe

#include<cstdio> #include<cstring> using namespace std; bool used[1010],link[1010][1010]; int mat[1010]; int n,k; bool find(int x) {for(int i=1;i<=n;i++){if(link[x][i]&&!used[i]){used[i]=1;if(mat[i]==-1||find(mat[i])){mat[i]=x;return 1;}}}return 0; } int main() {scanf("%d%d",&n,&k); for(int i=1;i<=k;i++){int r,c;scanf("%d%d",&r,&c);link[r][c]=1;}int all=0;memset(mat,-1,sizeof(mat)); for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(find(i))all++;}printf("%d\n",all);return 0; }

總結

以上是生活随笔為你收集整理的POJ-3041 匈牙利算法 二分图最大匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。