HDU5727 Necklace
2024-09-21 06:39:21
http://acm.hdu.edu.cn/showproblem.php?pid=5727
题意:n个珠子,每个珠子有阴阳两种属性,且阴的一定和阳的紧邻,排成一个环;m行,每行两个数,表示阳性x珠子和y阴性珠子相邻则功能减弱,问功能减弱珠子最少有几个
思路:二分匹配
全排列阴性珠子,因为是环,O((n-1)!);枚举每个阳性珠子,插入i位置,前提是i前后两个阴性珠子都不与阳性珠子有排斥作用;
最后问题变转化成,阳性珠子和位置的最大匹配问题
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int M = 1e6+;
const int MOD = 1e9+;
#define LL long long
#define LB long double
#define mi() (l+r)>>1
double const pi = acos(-);
const double eps = 1e-;
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
int mp[][];
int a[];
int n,m;
int ans;
bool vis[];
int b[];
vector<int>s[];
bool dfs(int x){
if(vis[x]) return false;
vis[x]=;
for(int i=;i<(int)s[x].size();i++){
int v=s[x][i];
if(b[v]==-||dfs(b[v])){
b[v]=x;
return true;
}
}
return false;
} void hungarian(){
clc(b,-);
int tem=;
for(int i=;i<=n;i++){
clc(vis,);
if(dfs(i))
tem++;
}
if(tem>ans) ans=tem;
}
void work(){
for(int i=;i<n;i++){
a[i]=i+;
}
do{
for(int i=;i<=;i++) s[i].clear();
for(int i=;i<n;i++){
int k1=a[i],k2=a[(i-+n)%n];
for(int j=;j<=n;j++){
if(!mp[k1][j]&&!mp[k2][j]) s[j].push_back(i);
}
}
hungarian();
}while(next_permutation(a+,a+n)&&ans!=n);
}
int main(){
// fre();
while(~scanf("%d%d",&n,&m)){
clc(mp,);
ans=;
for(int i=;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
mp[y][x]=;
}
work();
printf("%d\n",n-ans);
}
return ;
}
最新文章
- NodeJs+Request+Cheerio 采集数据
- Adobe Photoshop CC (32/64位) 绿色精简版
- 也说php从mysql数据库通过服务器端json返回数据出现乱码问题
- Android中插件开发篇之----应用换肤原理解析
- [ucgui] 对话框2——小窗口初始化与消息响应
- 使用WCF对外提供接口
- More about dubbo
- 让浏览器屏蔽js
- Xcode-程序开发设计-01UIKit 框架
- Android Cursor类的概念和用法
- wordpress高级教程
- CloudXNS首次使用体验
- JSP之JavaBean
- [03-01]JDBC基础
- SQL语句:如何让字符串转化数字
- div css 图片和文字上下居中对齐
- OpenStack-Ocata版+CentOS7.6 云平台环境搭建 — 3.安装配置OpenStack认证服务(keystone)
- JVM内存区域划分及垃圾回收
- Codeforces.100633J.Ceizenpok&#39;s formula(扩展Lucas)
- 【TCP/IP】二、协议的概念
热门文章
- ExecutorService中submit和execute的区别
- iOS 精确定时器
- 244. Shortest Word Distance II
- android从应用到驱动之—camera(1)---程序调用流程
- 实例学习写Makefile文件
- python 有关矩阵行列的存取 np.array
- 【转载】React初学者入门须知
- 纯tarjan poj2186
- sharepoint Linq方式的增,删,查,改
- 无法加载 DLL“rasapi32.dll”: 动态链接库(DLL)初始化例程失败。