标签存档：图论

【算法分析】

很简单，属于送分题类型。。。

缩点然后topsort+dp就可以了~

但是比较纠结的是会爆栈。。。。比赛不知道会不会的？听说Linux的栈比较大吧。。。

【CODE】

#include #include #include const int N=501111;
const int INF=1000000000;
struct gtp{int x,y,next;}g[N];
int n,e,tot,S,head,tail,ans,stack;
int ls[N],fa[N],color[N],dep[N],list[N],du[N],w[N],F[N],v[N],edge[N],p[N];
bool ed[N];

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

void input(){
     int m,x,y;
     scanf("%d%d",&n,&m);
     for (int i=1;i<=m;i++){
         scanf("%d%d",&x,&y);
         addedge(x,y);
     }
     for (int i=1;i<=n;i++) scanf("%d",&w[i]);
     int num;
     scanf("%d%d",&S,&num);
     for (int i=1;i<=num;i++){
         scanf("%d",&x);
         ed[x]=true;
     }
}

int gf(int k){
    if (fa[k]==k) return k;
    fa[k]=gf(fa[k]);
    return fa[k];
}

void dfs(int k){
/*    
     for (int t=ls[k];t;t=g[t].next)
       if (!dep[g[t].y]){
         dep[g[t].y]=dep[k]+1;
         dfs(g[t].y);
         if (dep[gf(g[t].y)]       }else
       if (!color[gf(g[t].y)] && dep[gf(g[t].y)]         fa[k]=fa[g[t].y];
     color[k]=1;
*/
     stack=1; p[1]=k; edge[1]=ls[k];
     while (stack){
           int &t=edge[stack];
           if (!t){
             color[p[stack]]=1;
             stack–;
             continue;
           }
           if (!dep[g[t].y]){
             dep[g[t].y]=dep[g[t].x]+1;
             stack++;
             p[stack]=g[t].y;
             edge[stack]=ls[g[t].y];
           }else
           if (!color[gf(g[t].y)] && dep[gf(g[t].y)]             fa[g[t].x]=fa[g[t].y];
             edge[stack]=g[edge[stack]].next;
           }else edge[stack]=g[edge[stack]].next;
     }
}

void tarjan(){
     for (int i=1;i<=n;i++){
         fa[i]=i;
         color[i]=0;
         dep[i]=0;
     }
     for (int i=1;i<=n;i++)
       if (!dep[i]){
         dep[i]=1;
         dfs(i);
       }
     for (int i=1;i<=n;i++){
         gf(i);
         if (fa[i]!=i){
           w[fa[i]]+=w[i];
           if (ed[i]) ed[fa[i]]=true;
         }
     }
}

void changegraph(){
     int te=e;
     e=0; memset(ls,0,sizeof(ls));
     for (int i=1;i<=te;i++)
       if (fa[g[i].x]!=fa[g[i].y])
         addedge(fa[g[i].x],fa[g[i].y]);
}

void topsort(){
     memset(du,0,sizeof(du));
     head=0; tail=0;
     for (int i=1;i<=e;i++) du[g[i].y]++;
     for (int i=1;i<=n;i++)
       if (fa[i]==i && !du[i]) list[++tail]=i;
     while (head           head++;
           for (int t=ls[list[head]];t;t=g[t].next){
             du[g[t].y]–;
             if (!du[g[t].y]) list[++tail]=g[t].y;
           }
     }
}

void dp(){
     memset(v,0,sizeof(v));
     for (int i=1;i<=n;i++) F[i]=-INF;
     ans=0;
     head=1;
     while (list[head]!=fa[S]) head++;
     F[fa[S]]=0;
     for (int k=head;k<=tail;k++){
       int &i=list[k];
       if (F[i]==-INF) continue;
       F[i]+=w[i];
       for (int t=ls[i];t;t=g[t].next)
         if (v[g[t].y]!=i){
           v[g[t].y]=i;
           if (F[i]>F[g[t].y]) F[g[t].y]=F[i];
         }
       if (ed[i] && F[i]>ans) ans=F[i];
     }   
     printf("%dn",ans);
}

int main(){
    freopen("atm.in","r",stdin);
    freopen("atm.out","w",stdout);
    input();
    tarjan();
    changegraph();
    topsort();
    dp();
}

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1001

【题目大意】给出一个矩阵型的图，求左上角到右下角的最小割。边都是无向的。

【算法分析】把面看成图，然后可以通过跨越边的方式到达另外一端，跨过边就相当于去这条边为割集的一部分，最后求右上角这个面，到最下角这个面的最短路即可

【其它】NWA，注意N=1 OR M=1的情况请特判。

【CODE】

#include

【题目大意】

中文的，自己看吧。。。

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1093

【算法分析】

先缩点，然后topsort。

很容易知道，必须是一条长链才可以成为一个半连通分量。

如果有分叉，那么分叉的两端不能互相到达（已缩环），除非他们仍然可以表述为一条长链。

【其它】2WA，1A，居然有个地方漏写了,Orz

9420 edward_mj 1093 Accepted 15136K 2777MS G++ 2.98K 2010-02-12 23:57:46

【CODE】

#include

【题目大意】和K取方格数差不多，不过源和汇的连边有点改变。

【算法】最大费用最大流

【其它】1A

【CODE】

#include using namespace std;
const int N=600;
const int inf=0x7FFFFFFF/2-10;
struct gtp{int x,y,next,op,c,w;}g[100000];
int s,n,m,sn,en,e,S,T,cost;
int ls[N],d[N],fa[N],list[N],v[N],wz[N][N];

inline void add(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].w=w;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].w=-w;
    g[e].next=ls[y]; ls[y]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    scanf("%d%d%d%d",&sn,&en,&n,&m);
    int tot=0;
    for (int j=0;j<=n;j++)
      for (int i=0;i<=m;i++) wz[i][j]=++tot;
    S=(n+1)*(m+1)+1;
    T=S+1;
    for (int i=0;i<=n;i++)
      for (int j=1;j<=m;j++){
          int x;
          scanf("%d",&x);
          add(wz[j-1][i],wz[j][i],1,x);
          add(wz[j-1][i],wz[j][i],inf,0);
      }
    for (int j=0;j<=m;j++)
      for (int i=1;i<=n;i++){
          int x;
          scanf("%d",&x);
          add(wz[j][i-1],wz[j][i],1,x);
          add(wz[j][i-1],wz[j][i],inf,0);
      }
    for (int i=1;i<=sn;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(S,wz[z][y],x,0);
    }
    for (int i=1;i<=en;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(wz[z][y],T,x,0);
    }
}

bool spfa(){
    for (int i=0;i<=T;i++) d[i]=-inf;
    memset(v,0,sizeof(v));
    int head=0,tail=1;
    list[1]=S; v[S]=1; d[S]=0;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }
          }
        v[list[head]]=0;
    }
    if (d[T]==-inf) return false;
    return true;
}

void change(){
    int nf=inf,i=T;
    nf=0x7FFFFFFF;
    for (;i!=S;i=g[fa[i]].x)
      if (g[fa[i]].c    for (i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
    cost+=nf*d[T];
}

void maxflow(){
    cost=0;
    while (spfa())
      change();
}

int main(){
    freopen("robo0.in","r",stdin);
    freopen("robo0.ans","w",stdout);
    init();
    maxflow();
    printf("%dn",cost);
    return 0;
}

【题目】

【算法分析】

详细的看这里吧：http://www.byvoid.com/blog/noi-2008-employee/

【其它】最后一个点在我机器上TLE。。。BYV大牛的程序也是。。。算了，都差不了多少秒。

【CODE】

#include #include const int N=1111;
const int M=11111;
const int E=100000;
const int inf=0x7FFFFFFF;
struct gtp{int x,y,next,op,c,w;}g[E];
int n,m,S,T,e,cost,flow,tot;
int need[N],st[M],ed[M],cc[M];
int ls[N],d[N],fa[N],list[N],v[N],zz[N];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&need[i]);
    for (int i=1;i<=m;i++)
      scanf("%d%d%d",&st[i],&ed[i],&cc[i]);
}  

void add(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].op=e+1;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].op=e-1;
    g[e].next=ls[y]; ls[y]=e;
}   

void build(){
    S=n+2; T=n+3;
    for (int i=0;i<=n;i++)
      if (need[i]-need[i+1]>0) add(S,i+1,need[i]-need[i+1],0);
                          else add(i+1,T,need[i+1]-need[i],0);
    for (int i=2;i<=n+1;i++) add(i-1,i,inf,0);
    for (int i=1;i<=m;i++)
      add(ed[i]+1,st[i],inf,cc[i]);
}   

bool spfa(){
    memset(d,50,sizeof(int)*(T+1));
    tot=0;
    d[S]=0;
    int head=0,tail=1; list[1]=S;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }   
          }   
        v[list[head]]=0;
    }   
    if (d[T]!=d[0]) return true;
    return false;
}   

void change(){
    int nf=inf;
    for (int i=T;i!=S;i=g[fa[i]].x)
      if (g[fa[i]].c    cost+=nf*d[T];
    flow+=nf;
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }   
}   

void maxflow_mincost(){
    flow=0; cost=0;
    while (spfa())
      change();
    printf("%dn",cost);
}   

int main(){
    init();
    build();
    maxflow_mincost();
    return 0;
}