分类存档：默认分类

【题目大意】求一个无向图的最大密度子图

【算法分析】

这里有论文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;
}   

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

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

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

【code】

#include

【题目大意】求最小生成树是否唯一

【算法分析】使用prim算法，如果某一次加入的点是被几个已选点都更新过，且更新所得D值相等的话，必然导致多解。

【code】

#include

【题目大意】给定N个货币和M种兑换方式，问能否不断加钱？

【算法分析】用spfa算法判断有无正权回路。如果一个点进入队列超过N次。。。那就是有正权了。

【其它】注意精度要控制一下

【code】

#include #include #include #include using namespace std;
struct gtp{int x,y,next;double rate,sui;}g[201];
double d[101],sm;
int v[101],list[101],n,e,st,ls[101],insnum[101];

inline void addedge(int x,int y,double rate,double sui){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
       g[e].rate=rate; g[e].sui=sui;
}

void init(){
     int m; e=0;
     scanf("%d%d%d%lf",&n,&m,&st,&sm);
     for (int i=1;i<=m;i++){
         double rate,sui;
         int xx,yy;
         scanf("%d%d%lf%lf",&xx,&yy,&rate,&sui);
         addedge(xx,yy,rate,sui);
         scanf("%lf%lf",&rate,&sui);
         addedge(yy,xx,rate,sui);
     }
}

bool spfa(){
     memset(d,0,sizeof(d));
     memset(v,0,sizeof(v));
     memset(insnum,0,sizeof(insnum));
     v[st]=1; d[st]=sm; insnum[st]=1; list[0]=st;
     int head=-1,tail=0;
     while (head!=tail){
           head++; if (head>100) head=0;
           for (int t=ls[list[head]];t!=0;t=g[t].next)
             if ((d[g[t].x]-g[t].sui)*g[t].rate>=d[g[t].y]+1e-6){
               d[g[t].y]=(d[g[t].x]-g[t].sui)*g[t].rate;
               if (v[g[t].y]==0){
                 v[g[t].y]=1;
                 tail++; if (tail>100) tail=0;
                 list[tail]=g[t].y;
                 insnum[g[t].y]++;
                 if (insnum[g[t].y]>n) return true;
               }
             }
           v[list[head]]=0;
     }
     return false;
}

int main(){
    init();
    if (spfa()) printf("YESn");
           else printf("NOn");
}

【题目大意】给定一个有向图，求从S走到F（最短路）和（最短路长度+1）的方案总和。

【算法分析】用dijkstra+heap求出最短路和次短路的方案和长度。如果最短路和次短路的长度相差1，那么将方案数相加，否则直接输出

【其它】1A

【程序】

#include #include #include #define E 11111
#define N 1111*2
#define INF 0x7FFFFFFF/2
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int ls[N],d[N],c[N],list[N],n,e,st,ed,zz[N];
struct headtpy{
       int a[N],tot;
       void up(int k){
            while (k>1 && d[a[k]]                  swap(a[k],a[k/2]);
                  zz[a[k]]=k; zz[a[k/2]]=k/2;
                  k/=2;
            }
       }
       void down(int k){
            while (k*2<=tot){
                  int t=k*2;
                  if (t+1<=tot && d[a[t+1]]                  if (d[a[k]]>d[a[t]]){
                    swap(a[k],a[t]);
                    zz[a[k]]=k; zz[a[t]]=t;
                    k=t;
                  }
                  else break;
            }
       }
       void ins(int locate){
            tot++;
            a[tot]=locate;
            zz[locate]=tot;
            up(tot);
       }
       void del(){
            a[1]=a[tot];
            tot–;
            down(1);
       }
}heap;

void init(){
     scanf("%d%d",&n,&e);
     memset(ls,0,sizeof(ls));
     memset(zz,0,sizeof(zz));
     for (int i=1;i<=e;i++){
         int x,y,w;
         scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
         g[i].next=ls[g[i].x]; ls[g[i].x]=i;
     }
     scanf("%d%d",&st,&ed);
     for (int i=1;i<=2*n;i++){
         d[i]=INF;
         c[i]=0;
     }
     d[st*2-1]=0; c[st*2-1]=1;
     heap.tot=0;
     for (int i=1;i<=2*n;i++) heap.ins(i);
}

inline void push(int td,int tc,int ty){
       if (td         d[ty*2]=d[ty*2-1];
         c[ty*2]=c[ty*2-1];
         heap.up(zz[ty*2]);
         d[ty*2-1]=td;
         c[ty*2-1]=tc;
         heap.up(zz[ty*2-1]);
       }
       else if (td==d[ty*2-1]) c[ty*2-1]+=tc;
       else if (td              d[ty*2]=td;
              c[ty*2]=tc;
              heap.up(zz[ty*2]);
            }
       else if (td==d[ty*2]) c[ty*2]+=tc;
}

void dijkstra(){
     while (heap.tot>0){
           int p=(heap.a[1]+1)/2;
           for (int t=ls[p];t!=0;t=g[t].next)
             push(d[heap.a[1]]+g[t].w,c[heap.a[1]],g[t].y);
           heap.del();
     }
     if (d[ed*2-1]+1==d[ed*2]) printf("%dn",c[ed*2-1]+c[ed*2]);
                          else printf("%dn",c[ed*2-1]);
}

int main(){
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
        init();
        dijkstra();
    }
}