【题目大意】给定一个N*M得矩阵，#表示不可以走，0..9表示走到这上面可以得到的分数（每个点只能采集一次）一开始你在左上角，只能向下走或向右走。然后有一些地方有传送门，可以选择无耗损地从这一点传到目标点，也可以选择不传，问最多能得到多少分。
【算法分析】先缩点，然后拓扑排序，最后用dp求最长路，输出就行了。
【其它】悲剧，RE了N遍，不过又MS并非RE得问题，我一开始把不能走到的点也算到DP序列里去了，居然一直RE。。。搞不懂为什么。改了以后终于AC。
【CODE】
#include
[POJ 2404] 中国邮递员问题、一般图最小权匹配、欧拉回路
【题目大意】给定一个无向图，让你求从其中一个点出发，经过所有边，回到这个点（边可以重复走）的最短总长度。
【算法分析】
如果是直接给欧拉图的话，就是输出边权和就可以了。
否则的话，就先floyed，然后求出任意两点的最短路。
然后给每对度为奇数的点连边，然后就是求一般无向图的最小权匹配了。
这个有经典算法的，叫带花树，不过我不会
所以，只能用状态压缩动态规划水过。
【其它】暴力47MS。。。
【程序】
#include
[POJ 1386] 判断是否存在欧拉路径
[POJ 3694] 双连通分量、lca、tarjan、缩环
【题目大意】给定一个无向连通图，每次操作是在原图上加一条边，对于每次操作，输出剩下多少桥。
【算法分析】
什么是桥？就是去掉这条边以后图不再连通了。
试想一下如果缩环以后会把这个图弄成一棵树会怎样呢？
那就是树中的每条边都是割边（环上的不可能是割边）。
于是我们可以先用tarjan缩点，然后建起这颗树来。
每次如果添加边的话，那么就找那两个点对应的点的lca。
然后找lca路径上的点都缩到lca上去。
这样每条边只会常数次。所以总时间复杂度为O(E)。
【HINT】一开始SB了，想了很久，以为要把边做一下调整，后来才发现根本不用，因为树中的边肯定不可能是重边，否则那两个点都已经合成一个了。。。
【其他】居然1A，真不敢相信
纪念一下，刚好10000K内存。。。我保证，我只交了一次。。。而且没算过内存。。。
6324346 edward2 3694 Accepted 10000K 422MS C++ 2731B 2010-01-09 23:48:06
【程序】
#include
[POJ 3155] 最大密度子图、最大权闭合图、分数规划、求最小割
【题目大意】求一个无向图的最大密度子图
【算法分析】
这里有论文http://u.115.com/file/f7142414ae 最小割.pdf
我是直接套最大权闭合图来做的。
首先
密度P=Ex / Vy
0=Ex / Vy – P
令H=Ex / Vy – P
则两边同乘Vy得：H * Vy = Ex – P * Vy
由于该式满足单调性，于是我们可以二分P，使得H=0时，就可以取得P的确切值。
而式子右边则是最大权闭合图的计算定义，于是我们可以直接套用最大权闭合图求解。
【HINT】注意精度和H最后必须>0，否则你求得的是没有任何一个点，因为H=0时最大权闭合图的方案应该是一个点也不取，只要让它稍微>0，就可以利用割找到取了哪些点了。
【其它】交了34次，做了1个月，终于AC
【程序】
#include
#define eps2 1e-6
#define INF 1e20
#define N 100000
using namespace std;
struct gtp{int x,y,next,op;double c;}g[N];
int n,m,e,ls[N],d[N],fa[N],cur[N],num[N],mark[N],edge[N][2],S,T,ans=0;
void init(){
for (int i=1;i<=m;i++)
scanf("%d%d",&edge[i][0],&edge[i][1]);
}
void relabel(int k){
int mm=T;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c>0) mm=min(mm,d[g[t].y]);
d[k]=mm+1;
}
double change(){
double flow=INF;
for (int i=T;i!=S;i=g[fa[i]].x) flow=min(flow,g[fa[i]].c);
for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=flow;
g[g[fa[i]].op].c+=flow;
}
return flow;
}
double sap(){
double flow=0;
for (int i=S;i<=T;i++){
d[i]=0;
cur[i]=ls[i];
num[i]=0;
}
num[0]=T+1;
int i=S;
while (d[S]
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
else cur[i]=g[cur[i]].next;
if (cur[i]==0){
if (–num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
flow+=change();
i=S;
}
}
}
return flow;
}
void addedge(int x,int y,double c){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}
double check(double limit){
e=0; S=0; T=n+m+1;
memset(ls,0,sizeof(int)*(T+1));
for (int i=1;i<=n;i++) addedge(i,T,limit);
for (int i=1;i<=m;i++){
addedge(S,n+i,1.0);
addedge(n+i,edge[i][0],INF);
addedge(n+i,edge[i][1],INF);
}
return m-sap();
}
void dfs(int k){
mark[k]=1;
if (k>0 && k<=n) ans++;
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c>0 && mark[g[t].y]==0)
dfs(g[t].y);
}
void solve(){
if (m==0){
printf("1n1n");
return;
}
init();
double l=0,r=m,mid,ret;
while (l+eps
ret=check(mid);
if (fabs(ret)
for (int t=ls[0];t!=0;t=g[t].next)
if (g[t].c>0){
flag=true;
break;
}
if (flag) break;
r=mid-eps;
}
else l=mid+eps;
}
memset(mark,0,sizeof(int)*(T+1));
ans=0;
dfs(S);
printf("%dn",ans);
for (int i=1;i<=n;i++)
if (mark[i]==1) printf("%dn",i);
}
int main(){
while (scanf("%d%d",&n,&m)!=EOF) solve();
return 0;
}