[关键字]&＃xff1a;图论 二分图匹配
[题目大意]&＃xff1a;太麻烦&＃xff0c;就不说了
//&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
[分析]&＃xff1a;因为每个距离都对应着两个数字——就是&＃43;d或-d&＃xff0c;这样0~n-1和它所转换的序列可以看成一个二分图的模型&＃xff0c;而一个完备匹配就对应着一个序列。只要求一遍最大匹配看是否等于n。而字典序的问题&＃xff0c;因为用匈牙利算法找增广路就是找到第一个没有被匹配或和它匹配的点可以找到另外一条增广路的点&＃xff0c;这样每次都是将已经匹配过的点所匹配的点编号变大&＃xff0c;如果倒着找匹配就恰好能保证序号越小就越可以找到编号小的点匹配。
[代码]&＃xff1a;
View Code #include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN&＃61;20000;
int n;
int m1[MAXN],m2[MAXN];
bool v[MAXN];
vector<int> e[MAXN];
void Init()
{
int t1,t2,d;
scanf("%d",&n);
for (int i&＃61;0;i
scanf("%d",&d);
t1&＃61;i&＃43;d;
if (t1>&＃61;n) t1%&＃61;n;
t2&＃61;i-d;
if (t2<0) t2&＃43;&＃61;n;
if (t1>t2) swap(t1,t2);
e[i].push_back(t1),e[i].push_back(t2);
}
}
bool DFS(int u)
{
for (vector<int>::iterator i&＃61;e[u].begin();i
{
v[*i]&＃61;1;
if (m2[*i]&＃61;&＃61;-1 || DFS(m2[*i]))
{
m1[u]&＃61;*i;
m2[*i]&＃61;u;
return 1;
}
}
return 0;
}
void Solve()
{
memset(m1,255,sizeof(m1));
memset(m2,255,sizeof(m2));
int ans&＃61;0;
//for (int i&＃61;0;i
for (int i&＃61;n-1;i>&＃61;0;--i)
{
memset(v,0,sizeof(v));
if (DFS(i)) &＃43;&＃43;ans; else break;
}
if (ans!&＃61;n) printf("No Answer\n");
else
{
printf("%d",m1[0]);
for (int i&＃61;1;i
}
}
int main()
{
Init();
Solve();
system("pause");
return 0;
}
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号