本文主要是介绍hdu4619 - Warm up 2(联通图or贪心0r二分图匹配)【待完善】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题好多种做法，，，
1、联通图。
由于题目特点，这道题可以转化为求图的该图的各个子联通图，每个包含x个点的联通图都可以最多得到不重叠的x/2个牌。
注意这句话：很重要的（It's guaranteed the dominoes in the same direction are not overlapped, but horizontal and vertical dominoes may overlap with each other.）
代码如下：
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define M 2005
int n, m, u[M][2], v[M][2];
bool vis[150][150];
vector<int>g[150][150];
void dfs(int x, int y, int &tt)//遍历联通图得到节点数目
{vis[x][y] = 1;tt++;for(int i = 0; i < (int)g[x][y].size(); i++){int d = g[x][y][i];int xx = u[d][0], yy = u[d][1];if(vis[xx][yy]==0)dfs(xx,yy,tt);xx = v[d][0], yy = v[d][1];if(vis[xx][yy]==0)dfs(xx,yy,tt);}
}
int main ()
{int x, y;while(scanf("%d %d",&n,&m), n+m){for(int i = 0; i < 150; i++)for(int j = 0; j < 150; j++)g[i][j].clear();for(int i = 0; i < n; i++){scanf("%d %d",&x, &y);u[i][0] = x;u[i][1] = y;v[i][0] = x+1;v[i][1] = y;g[x][y].push_back(i);g[x+1][y].push_back(i);}for(int i = n; i < n+m; i++){scanf("%d %d",&x, &y);u[i][0] = x;u[i][1] = y;v[i][0] = x;v[i][1] = y+1;g[x][y].push_back(i);g[x][y+1].push_back(i);}memset(vis,0,sizeof(vis));int ans = 0, tt = 0;for(int i = 0; i < 150; i++)for(int j = 0; j < 150; j++)if(g[i][j].size()!=0&&vis[i][j]==0){tt = 0; dfs(i,j,tt); ans+=(tt/2);}printf("%d\n",ans);}return 0;
}
这篇关于hdu4619 - Warm up 2(联通图or贪心0r二分图匹配)【待完善】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
