【题目大意】N个点，向起点连一条权值为T的弧，然后根据描述将图连出来，求起点到点1的最短路。不过，每个点有一个等级限制，这条最短路上的最大等级和最小等级差不能超过M。
【算法分析】枚举一个等级范围，然后spfa即可。以前用topsort写的那个是错的= =。。。如果真的用topsort+dp的话还要缩点。。。
【其他】1A
【code】
#include
[POJ 3565] 最小费用流 利用重要性质
【题目大意】：给定2*N个点的坐标，让你用前N个点和后N个点一一配对，使得相连的边没有相交的。
【算法分析】：首先有一个性质必须知道，那就是最短的配对，必然是没有相交的。于是我们就可以构建二分图，求最小权匹配。（用最小费用流求解）
【code】
#include
[HDOJ 1914] 稳定婚姻系统
题意：
就是稳定婚姻系统的模板题。
对于求出来的每一组配对(a,b)，不能找到(b,c)满足b更喜欢c且c更喜欢b，对于a同样。
分析：
就使一种延迟方法，就使先让他们拍拖然后遇到更好的，就飞掉之前的伴侣。。。
有点邪恶。。。
更详细的讲解请参照：http://hi.baidu.com/leokan/blog/item/4f9b04f719993025730eecef.html
HINT:
1A。
code：
#include
int n,ml[27][27],fl[27][27],st[27],bf[27],gf[27],rank[27][27];
char mn[27],fn[27];
int pos(char ch){
if (ch>=’a’ && ch<='z'){
for (int i=1;i<=n;i++)
if (mn[i]==ch) return i;
}else
for (int i=1;i<=n;i++)
if (fn[i]==ch) return i;
}
void init(){
cin >> n;
for (int i=1;i<=n;i++) cin >> mn[i];
for (int i=1;i<=n;i++) cin >> fn[i];
for (int t=1;t<=n;t++){
char ch;
cin >> ch;
int i=pos(ch);
cin >> ch;
for (int j=1;j<=n;j++){
cin >> ch;
ml[i][j]=pos(ch);
}
}
for (int t=1;t<=n;t++){
char ch;
cin >> ch;
int i=pos(ch);
cin >> ch;
for (int j=1;j<=n;j++){
cin >> ch;
fl[i][j]=pos(ch);
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
rank[i][fl[i][j]]=j;
}
void dfs(int p){
int i;
for (i=st[p]+1;i<=n;i++){
if (bf[ml[p][i]]==0){
bf[ml[p][i]]=p;
gf[p]=ml[p][i];
break;
}
if (rank[ml[p][i]][p]
bf[ml[p][i]]=p;
gf[p]=ml[p][i];
dfs(tmp);
break;
}
}
st[p]=i;
}
void work(){
memset(st,0,sizeof(st));
memset(bf,0,sizeof(bf));
memset(gf,0,sizeof(gf));
for (int i=1;i<=n;i++)
if (gf[i]==0) dfs(i);
}
void print(){
for (int i=1;i<=n;i++)
cout << mn[i] << " " << fn[gf[i]] << endl;
}
int main(){
int T;
cin >> T;
for (int i=1;i<=T;i++){
init();
work();
print();
if (i!=T) cout << endl;
}
}
[ural 1129] 欧拉回路
题意：
幼儿园里有许多房间，之间是走廊和门。一个装修计划即将执行。 这些门允许涂上明快的颜色：绿色和黄色。园长希望满足以下条件：任意一扇门的各个面必须不同颜色。每一个房间绿色门的数量，与黄色门的数量之差最多为1。给定园长的计划，请提出你的安排。
分析：
首先，对于无向图，度为奇数的点必然有偶数个。
下面证明一下：
如果加入边(i,j)，有下面几种情况：
1、两个点原来的度一奇一偶，那么加入边以后，度为奇数的点的数量没变
2、两个点原来的度都是奇数，加入边后，度为奇数的点的数量-2
3、两个点原来的度都为偶数，加入边后，度为奇数的点的数量+2
由于只有3个种情况-2,+0,+2，所以，度为奇数的点的数量必为偶数个。
于是命题得证。
然后我们对度为奇数的同一连通分量的点连边，这样就使图不存在度为奇数的点了。
于是我们利用欧拉回路可以使颜色数量相等。
最后我们把加的边删掉。
由于每个点都只会加一条边，所以G和Y的差距不会超过1。
code：
#include
int g[101][101],n,ls[101][101],ct,du[101],L[100000],Lt,a[101][101],e=0,v[101];
bool flag[101];
void init(){
memset(g,0,sizeof(g));
scanf("%d",&n);
for (int i=1;i<=n;i++){
int num,tmp;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&tmp);
g[i][tmp]++;
}
}
}
void dfs(int k){
for (int i=1;i<=n;i++)
if (a[i][k]>0){
a[i][k]–;
a[k][i]–;
dfs(i);
}
L[++Lt]=k;
}
void filldfs(int k){
for (int i=1;i<=n;i++)
if (g[k][i]>0 && v[i]==0){
v[i]=v[k];
filldfs(i);
}
}
void fill_color(){
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++)
if (v[i]==0) {
v[i]=++ct;
filldfs(i);
}
}
void addcolor(int x,int y){
e++;
c[e].color=0;
c[e].next=ls[x][y];
ls[x][y]=e;
e++;
c[e].color=1;
c[e].next=ls[y][x];
ls[y][x]=e;
}
void eur(){
memset(du,0,sizeof(du));
memcpy(a,g,sizeof(g));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (g[i][j]>0) du[j]+=g[i][j];
for (int i=1;i<=n;i++)
if (du[i]%2==1)
for (int j=i+1;j<=n;j++)
if (du[j]%2==1 && v[i]==v[j]){
du[i]++;
du[j]++;
a[i][j]++;
a[j][i]++;
break;
}
memset(flag,false,sizeof(flag));
for (int i=1;i<=n;i++)
if (!flag[v[i]]){
flag[v[i]]=true;
Lt=0;
dfs(i);
for (int j=1;j
}
}
void print(){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
int t=ls[i][j];
for (int num=g[i][j];num>=1;num–){
if (c[t].color==0) printf("G ");
else printf("Y ");
t=c[t].next;
}
}
printf("n");
}
}
int main(){
init();
fill_color();
eur();
print();
}
[POJ 2762] 弱连通分量
题意：
给定N个点,E条边的有向图，问图中是否任意两个点u，v都有
（u能到达v）or（v能到达u）
分析：
首先环内的肯定是满足的，所以先缩点。
然后剩下一棵树。
那么从根节点（即缩点后没有入度的点）出发，假设一路走下去是一条链的话（即树没有分叉），而且所有的点都能走到，那么就满足性质。
证明：
1、如果有分叉的话，分叉两边的点不能到达对方。
2、入度为0的点不可能没有，因为已经缩点，不存在环了。
3、入度为0的如果>1，那么两个入度为0的点不能到达对方。
所以，结论就是，只有所有收缩后的点成一长链，才能满足性质。
插曲：
Tarjan居然写错了= =，真想抽自己一下
code：
#include