标签存档：图论

[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 #include #define eps 1e-9
#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]        while (cur[i]!=0)
          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        mid=(l+r)/2;
        ret=check(mid);
        if (fabs(ret)            bool flag=false;
            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;
}   

[POJ 3522] 求权和差最小的最小生成树

【题目大意】给定一个无向图，求它的一棵生成树，使得权最大的边的权和最小的边的权差值最小。

【算法分析】枚举最短的一条边，然后对权值大于它的边进行Kruskal。直到构建好最小生成树，看目前最大边和枚举的那条边的权值之差是否小于ans

【其它】本来1A的，居然因为G++编译器问题CE了一遍

【code】

#include