Then M lines followed, every line contains two integers X,Y, indicates that magic gem X with Yang energy will become somber adjacent with the magic gem Y with Yin energy.
Sample Input Sample Output
题意:
有2n个珠子,分成阴阳两极,每极各n个。用这2n个珠子做成一个项链,使得相邻两个珠子的极性是不一样的,有一些阳性的珠子会被一些阴性的珠子所削弱,在它们它们相邻的情况下。
给你m个关系[x,y]表示阳性珠子x会被阴性珠子y在相邻情况下所削弱。问你最少有多少个阳性被削弱。
思路:
固定阳珠,然后对阴珠进行全排列,枚举每一种情况,对于一种排列, 给每一个位置对应的不会褪色的阳珠建边, 做出二维数组,跑出的最大匹配就是最多的不褪色阳珠子个数。我们通过匈牙利算法算出最大匹配sum,然后算出n-sum,对于每种排列取最小值就得到了我们想要的答案,注意特判下n=0的情况。
代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MAX 0x3f3f3f3f int map[][];//map数组存的是阴阳珠是否消退,如果map[1][1]=1表示1号阳珠和1号阴珠能消退
int a[];//用来存储排列的方式
int g[][];//数组存的是排列后的阴阳珠能否消退 int linker[];//用来标记
int flag[];//用来标记 int n;//n对珠 bool dfs(int u)
{
for(int v=; v<=n; v++)
{
if(g[u][v]&&!flag[v])
{
flag[v]=true;
if(linker[v]==-||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
} int hungary()
{
int res=;
memset(linker,-,sizeof linker);
for(int u=; u<=n; u++)
{
memset(flag,false,sizeof(flag));
if(dfs(u))
res++;
}
return res;
} int main()
{
int m;
while(~scanf("%d%d",&n,&m))//有n对宝石,即n个阳,n个阴
{
if(n==)//如果0对,直接输出0
{
cout<<<<endl;
continue;
}
memset(map,,sizeof(map));//开始初始化为0,表示都不消退
for(int i=; i<=m; i++)
{
int a,b;
cin>>a>>b;
map[a][b]=;
}//更新map数组,能消退的标记为1
int ans=MAX;
for(int i=; i<=n; i++)
a[i]=i;//初始化a[i]数组为本身,一会用于全排列
do
{
for(int i=; i<=n; i++)//固定阳珠,阴珠全排列
{
for(int j=; j<=n; j++)
{
g[i][j]=;
//如果是第三个,则特判(因为是环形,所以第三个应该检查是否与第3个排列数的阳珠和第1个排列数的阳珠消退)
if(j==n)
{
//如果3号阳珠既不与第3个阴珠消退也不和第1个阴珠消退,标记为1,注意是排列之后的第一个和第三个
if(!map[i][a[j]]&&!map[i][])
g[i][j]=;
}
//如果阳珠不与相邻的两个阴珠消退,则标记为1
else if(!map[i][a[j]]&&!map[i][a[j+]])
{
g[i][j]=;
}
}
}
int num=hungary();//求出在此排列顺序中最大的匹配数
ans=min(ans,n-num);
}
while(next_permutation(a+,a+n+)); //全排列,排列出来的存在a数组中
cout<<ans<<endl;
}
return ;
}
HDU5727 Necklace(二分图匹配)的更多相关文章
-
hdu 5727 Necklace 二分图匹配
题目链接 给2*n个珠子, n<=9, n个阴n个阳. 然后将它们弄成一个环, 阴阳交替.现在给你m个关系, 每个关系给出a, b. 如果阳a和阴b挨着, 那么a就会变暗. 问你最小变暗几个阳. ...
-
hdu 5727 Necklace dfs+二分图匹配
Necklace/center> 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5727 Description SJX has 2*N mag ...
-
HDU 5727 Necklace(二分图匹配)
[题目链接]http://acm.hdu.edu.cn/showproblem.php?pid=5727 [题目大意] 现在有n颗阴珠子和n颗阳珠子,将它们阴阳相间圆排列构成一个环,已知有些阴珠子和阳 ...
-
HDU 5727 Necklace ( 2016多校、二分图匹配 )
题目链接 题意 : 给出 2*N 颗珠子.有 N 颗是阴的.有 N 颗是阳的.现在要把阴阳珠子串成一个环状的项链.而且要求珠子的放置方式必须的阴阳相间的.然后给出你 M 个限制关系.格式为 ( A.B ...
-
UVA 12549 - 二分图匹配
题意:给定一个Y行X列的网格,网格种有重要位置和障碍物.要求用最少的机器人看守所有重要的位置,每个机器人放在一个格子里,面朝上下左右四个方向之一发出激光直到射到障碍物为止,沿途都是看守范围.机器人不会 ...
-
POJ 1274 裸二分图匹配
题意:每头奶牛都只愿意在她们喜欢的那些牛栏中产奶,告诉每头奶牛愿意产奶的牛棚编号,求出最多能分配到的牛栏的数量. 分析:直接二分图匹配: #include<stdio.h> #includ ...
-
BZOJ1433 ZJOI2009 假期的宿舍 二分图匹配
1433: [ZJOI2009]假期的宿舍 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2375 Solved: 1005[Submit][Sta ...
-
HDU1281-棋盘游戏-二分图匹配
先跑一个二分图匹配,然后一一删去匹配上的边,看能不能达到最大匹配数,不能这条边就是重要边 /*----------------------------------------------------- ...
-
HDU 1083 网络流之二分图匹配
http://acm.hdu.edu.cn/showproblem.php?pid=1083 二分图匹配用得很多 这道题只需要简化的二分匹配 #include<iostream> #inc ...
-
BZOJ 1059 &; 二分图匹配
题意: 判断一个黑白染色的棋盘能否通过交换行或列使对角线上都是黑色. SOL: 真是有点醉...这种问题要么很神要么很水...第一眼感觉很水但就是不造怎么做...想了10分钟怎么感觉就是判断个数够不够 ...
随机推荐
-
仓库、超市、服装、食品、批发零售手持打印PDA开单器-现场无线开单扫描 无线传输电脑
深圳浩瀚技是一家主要从事手持数据终端硬件.软件研究.销售服务为一体的高新企业公司.公司主要销售进销存等无线开单系统.工业级手持PDA,安卓数据采集器,RFID阅读器等设备.我们秉承“诚信.敏捷.繁荣” ...
-
iOS是怎么";绘画";的?
什么是绘图引擎 如果您以前从事其它平台的图形/界面开发或者游戏开发,一定知道, 不管上层UI怎么呈现和响应, 底层必须有一个绘图引擎. iOS也不例外. 本文详细介绍了iOS Graphics的用法和 ...
-
linux 踢出用户方法
linux系统root用户可强制踢制其它登录用户, 首先以root登录以便查看全部的在线用户信息,可用w命令查看登录用户信息 强制踢人命令格式:pkill -kill -t tty 解释: pkill ...
-
使用POI进行Excel操作的总结一——创建Workbook,Sheet,Row以及Cell
前段时间,看在其他的网站上给出Excel文档的导入与导出操作,感觉很酷的样子,所以就学习了一下如何使用POI进行Excel的操作,现在对之前的学习过程进行一个总结. 一.现在普遍使用的Excel文档有 ...
-
linux杂记(二)主机硬盘规划
linux安装过程中,至少要两个partition,一个是[/],另一个是虚拟内存[swap].但比较不保险. 稍微麻烦点的方式: / /usr:linux操作系统 /home:使用者信息 /var: ...
-
codeforces 8D Two Friends 二分+ 判断三个圆是否有公共交点
题目链接 有两个人x, y, 现在在A点, x要直接去B点, y要先去C点在去B点, 现在给出x, y两人可以行走的最大距离T1, T2, 求出他们从A点出发之后, 可以走的最长的公共路径. 我们先看 ...
-
APP被苹果App Store拒绝的79个原因【转】
作为iOS开发者,估计有很多都遇到过APP提交到App Store被拒,然后这些被拒的原因多种多样,今天dApps收集了常见的被拒的原因,以便更多开发者了解. APP被苹果APPStore拒绝的各种原 ...
-
Minimum number of steps CodeForces - 805D(签到题)
D. Minimum number of steps time limit per test 1 second memory limit per test 256 megabytes input st ...
-
python安装提示No module named setuptools,wget提示ERROR 403: SSL is required
在下载安装一个python工具时提示报错No module named setuptools [root@kermit supervisor-3.3.0]$ sudo python setup.py ...
-
mysql 系统表的作用
mysql 的系统表记录了所有数据库表(包括视图的定义语句)的字段列,顺序,类型等等,知道这些的话可以做些抽取模板淫荡的操作吧 嘿嘿 public void shuaxinglb() { try { ...