裸的二分图匹配。需要输出方案。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define M 100005
#define N 65
bool vis[M];
vector<int> g[N];
int now[M];
int n,m;
int dfs(int k)
{
for(int i=0;i<g[k].size();i++)
{
int boy=g[k][i];
if(!vis[boy])
{
vis[boy]=1;
if(now[boy]==0||dfs(now[boy]))
{
now[boy]=k;
return 1;
}
}
}
return 0;
}
int main()
{
int a,b,ans;
int k;
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) g[i].clear();
memset(now,0,sizeof(now));
int maxn=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
maxn=max(maxn,b);
for(int j=a;j<=b;j++)
g[i].push_back(j);
}
ans=0;
for(int i=n;i>=1;i--)
{
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
printf("%d\n",ans);
int aa[66];
int top=0;
for(int i=1;i<=maxn;i++)
{
if(now[i])
{
aa[top++]=now[i];
}
}
sort(aa,aa+top);
for(int i=0;i<top;i++)
{
if(i) printf(" %d",aa[i]);
else printf("%d",aa[i]);
}
puts("");
}
return 0;
}
分享到:
相关推荐
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?n)⊕n,...
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. Output For each problem instance, output a ...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
HDUACM2010版13二分匹配及其应用.ppt
HDU 1022 Train Problem I 附详细思路
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)