HDU 1498 50 years, 50 colors (行列匹配+最小顶点覆盖)
题意:每个格子有不同颜色的气球用不同数字表示,每次可选某一行 或某一列来戳气球。每个人有K次机会。求最后哪些气球不能在
k次机会内被戳破。将这些气球的编号按升序输出。
分析:行列匹配,每种颜色的气球都要判断,故dfs传参时加一个气球的
编号。
感想:1、开始以为要按照最大匹配数按升序排列,昨天wa了一下午,把我搞郁闷了。
今天重新看题,是要按照id来排序。
2、学习了vector的用法,以前都不会用。。。这个之后汇总了再。。。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; struct node { int id; int cnt; }t[55]; int g[110][110]; int match[110]; int vis[110]; int n; vector<int> myv; bool cmp(node a,node b) { return a.cnt>b.cnt; } bool dfs(int u,int v) { for(int i=0;i<n;i++) { if(g[u][i]==v && !vis[i]) { vis[i]=true; if(match[i]==-1||dfs(match[i],v)) { match[i]=u; return true; } } } return false; } int main() { int k,i,p,flag,j; while(scanf("%d%d",&n,&k)&&n&&k) { flag=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) scanf("%d",&g[i][j]); } memset(t,0,sizeof(t)); for(p=1;p<=50;p++) { memset(match,-1,sizeof(match)); t[p].id=p; for(i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i,p)) t[p].cnt++; } } sort(t+1,t+51,cmp); myv.clear(); for(j=1;j<=50;j++) { if(t[1].cnt<=k) break; flag=1; if(t[j].cnt>k) myv.push_back(t[j].id); } sort(myv.begin(),myv.end()); if(flag) { for(i=0;i<myv.size();i++) printf("%d%c",myv[i],i==myv.size()-1?'\n':' '); } if(!flag) printf("-1\n"); } return 0; }
积累:
对vector中的元素排序:
头文件#include<algorithm>
vector<int> arr;
//输入数据
sort(arr.begin(),arr.end());
补充:软件开发 , C++ ,