edward_mj

[SGU 183]动态规划、优化

【题目大意】给出分给给N个球涂色的代价，让你给某些球涂色，使得满足任意连续M个球中至少有2个是已经涂色的。

【算法分析】易得方程F[I,J]=min(F[J,K])+A[I] (K

【其它】2WA，一次是瞎扯，根本理解错题意，一次是某个地方i1打成i了。

997585 09.02.10 12:51 edward 183 .CPP Accepted 143 ms 95 kb

【CODE】

#include #include #define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
const int N=11111;
const int M=111;
const int inf=(0x7FFFFFFF-5)/4;
int n,m,a[N],f[M][M],g[M][M],mod;
void init(){
    mod=M;
    memset(f,50,sizeof(f));
    memset(g,50,sizeof(g));
    for (int i=2;i<=m;i++)
      for (int j=1;j        f[i][j]=a[i]+a[j];
    for (int i=2;i<=m;i++){
        g[i][i-1]=f[i][i-1];
        for (int j=i-2;j>=1;j–)
          g[i][j]=min(f[i][j],g[i][j+1]);
    }
}

void work(){
    for (int i1=m+1;i1<=n;i1++){
      int i=i1%mod;
      memset(f[i],50,sizeof(f[i]));
      memset(g[i],50,sizeof(g[i]));
      for (int j1=i1-m+1;j1          int j=j1%mod;
          f[i][j]=g[j][(i1-m)%mod]+a[i1];
      }
      g[i][(i1-1)%mod]=f[i][(i1-1)%mod];
      for (int j1=i1-2;j1>=i1-m+1;j1–){
          int j=j1%mod;
          g[i][j]=min(g[i][(j+1)%mod],f[i][j]);
      }
    }
}

void print(){
    int ans=0x7FFFFFFF;
    for (int i=n-m+2;i<=n;i++)
      for (int j=n-m+1;j        if (f[i%mod][j%mod]    printf("%dn",ans);
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n<=m){
        int min1=0x7FFFFFFF,min2=0x7FFFFFFF;
        for (int i=1;i<=n;i++)
          if (a[i]              min2=min1;
              min1=a[i];
          }
          else
          if (a[i]        printf("%dn",min1+min2);
        return 0;
    }
    init();
    work();
    print();
    return 0;
}

[HDU 3313]最大流、有向图有源汇的割点**

【题目大意】给定一个有向图和源汇，求图中割点的个数

【算法分析】这题比较神，做法是将每个点拆点，然后中间连边流量为1，图中的边连边流量为inf，然后比较特殊的是S和T所拆得点间流量为2。然后这样的话，如果流量为2，那么图中除了S和T没有割点。如果流量为1，那么增广路上的有可能是割点，然后利用求最小割的dfs算法求出各个割。如果流量为0的话，那么说明S和T本来就不连通，所以任何一个点都是割点。

【其它】1WA，因为flow=2时特判错了，写成了0.低级错误啊…

2078969 2010-02-09 15:56:54 Accepted 3313 3156MS 12964K 2496 B G++ cwj

【CODE】

#include #include const int N=222222;
const int inf=(0x7FFFFFFF–10)/2;
struct gtp{int x,y,c,op,next;}g[1000000];
int n,m,e,S,T,ls[N],fa[N],v[N],list[N],ans,zgl[N],tt;

void addedge(int x,int y,int c){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; 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].op=e–1;
    g[e].next=ls[y]; ls[y]=e;
}

void init(){
    e=0;
    memset(ls,0,sizeof(ls));
    memset(zgl,0,sizeof(zgl));
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x+n,y,inf);
    }
    scanf("%d%d",&S,&T);
    for (int i=0;i<n;i++)
      if (i!=S && i!=T) addedge(i,i+n,1);
                   else addedge(i,i+n,2);
    T+=n;
}

bool bfs(){
    for (int i=0;i<2*n;i++) v[i]=0;
    int head=0,tail=1;
    list[1]=S;
    while (head!=tail){
        head++;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (!v[g[t].y] && g[t].c){
              v[g[t].y]=1;
              tail++;
              list[tail]=g[t].y;
              fa[g[t].y]=t;
          }
    }
    if (v[T]) return true;
    return false;
}

void change(){
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c–;
        g[g[fa[i]].op].c++;
        zgl[i]=1;
    }
    zgl[S]=1;
}

int ek(){
    bool flag=bfs();
    if (!bfs()) return 0;
    change();
    flag=bfs();
    if (!bfs()) return 1;
    return 2;
}

void dfs(int k){
    tt++;
    list[tt]=k;
    v[k]=1;
    for (int t=ls[k];t;t=g[t].next)
      if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}

void work(){
    g[ls[S]].c=0;
    g[ls[T–n]].c=0;
    memset(v,0,sizeof(v));
    ans=0;
    int st=S;
    for (;;){
        tt=0;
        dfs(st);
        bool flag=false;
        for (int i=1;i<=tt;i++) if (!flag)
          for (int t=ls[list[i]];t;t=g[t].next)
            if ((t&1) && !g[t].c && !v[g[t].y]){
                ans++;
                flag=true;
                st=g[t].y;
                if (g[t].y==T) return;
            }
    }
}

int main(){
    while (scanf("%d%d",&n,&m)!=EOF){
        init();
        if (S+n==T){
            printf("1n");
            continue;
        }
        int flow=ek();
        if (flow==0) printf("%dn",n);
        else
        if (flow==2) printf("2n");
        else{
            work();
            printf("%dn",ans);
        }
    }
}

[HDU 3311]状态压缩、spfa扩展、有多余点的最小生成树**

【题目大意】

给定N个寺庙，和M个另外的地方。

然后给定点权，表示在这个点挖水井需要的代价。

再给定边权，为建造无向边i，j的代价。

然后求怎样弄最小的代价使得前N个点，就是寺庙都能得到水。

【算法分析】

我是这样想的，实际上如果把所有的水井都当成一个点S，点权转化为S与该点连边的权值。这样就相当于求用最小的代价，使得S和前N个点成为同一连通分量。

由于可以有多余的点，所以不能MST。

我们可以设D[I,J]表示目前到达第i个点，然后前N个点，包括新增点S的遍历情况为j(j用二进制表示)

然后用spfa扩展，最后求最小的d[i][(1<<(n+1))-1]就行了

【其它】WA几次，然后找来xt大牛的程序对拍。。。发现随机小数据随了几百个（用bat）全部答案一样，于是就囧了。。。

最后发现居然是：spfa的队列大小没有*64

由于XT大牛在比赛之后没有交，于是偶很可耻地成了本题放出来以后第一个AC的烧饼

Rank Author Exe. Time Exe. Memory Code Len. Language Date 1 cwj 1343MS 1136K 1895B G++ 2010-02-07 17:32:39

【CODE】

#include #include const int E=40000;
const int N=2000;
const int N2=N*64;
struct gtp{int y,w,next;}g[E];
int n,m,p,e;
int ls[N],d[N][64],point[N2],state[N2];
bool v[N][64];

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

void init(){
    e=0; memset(ls,0,sizeof(ls));
    for (int i=1;i<=n+m;i++){
        int x;
        scanf("%d",&x);
        addedge(0,i,x);
        addedge(i,0,x);
    }
    for (int i=1;i<=p;i++){
        int x,y,w;
        scanf("%d %d %d",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
    }
}

void spfa(){
    memset(d,50,sizeof(d));
    memset(v,false,sizeof(v));
    int head=0,tail=0;
    for (int i=0;i<=n+m;i++) d[i][0]=0;
    for (int i=0;i<=n;i++){
        d[i][1<<i]=0;
        tail++;
        point[tail]=i;
        state[tail]=1<<i;
        v[i][1<<i]=true;
    }
    while (head!=tail){
        head++; if (head>=N2) head=0;
        for (int t=ls[point[head]];t;t=g[t].next)
          for (int ts=0;ts<(1<<(n+1));ts++)
            if (d[point[head]][state[head]]+g[t].w+d[g[t].y][ts]<d[g[t].y][ts|state[head]]){
                d[g[t].y][ts|state[head]]=d[point[head]][state[head]]+g[t].w+d[g[t].y][ts];
                if (!v[g[t].y][ts|state[head]]){
                    v[g[t].y][ts|state[head]]=true;
                    tail++; if (tail>=N2) tail=0;
                    point[tail]=g[t].y;
                    state[tail]=(ts|state[head]);
                }
            }
        v[point[head]][state[head]]=false;
    }
}

int main(){
    while (scanf("%d %d %d",&n,&m,&p)!=EOF){
        init();
        spfa();
        int ans=0x7FFFFFFF;
        for (int i=0;i<=n+m;i++)
          if (d[i][(1<<(n+1))-1]<ans) ans=d[i][(1<<(n+1))-1];
        printf("%dn",ans);
    }
}

[HDU 3306]矩阵乘法、神一般的构造**

【题目大意】

f(0)=1,f(1)=1

给出递推式f(n)=x*f(n-1)+y*f(n-2)

令s(n)=f(0)^2+f(1)^2+……+f(n)^2

【算法分析】矩阵乘法，但是感觉这简直是神来之笔。。。

构造矩阵[S(n) A(n-1)^2 A(n)*A(n-1) A(n)^2]

转移的话乘这个矩阵

| 1 0 0 0 |

| Y^2 0 0 Y^2 |

| 2*X*Y 0 Y 2*X*Y |

| X^2 1 X X^2 |

【其它】WA了N遍，发现init矩阵的时候也要取余，因为有平方，X,Y<=2^31的话，乘起来就到int64了，然后矩阵乘法那里也可能爆，所以必须先取余

2073791 2010-02-07 14:46:22 Accepted 3306 687MS 220K 1660 B G++ cwj

【CODE】

#include #include const __int64 mod=10007;
__int64 c[4][4],a[4][4],t[4][4],p[4][4],n,x,y;

void init(){
    a[0][0]=2;
    a[0][1]=1;
    a[0][2]=1;
    a[0][3]=1;
    c[0][0]=1;    c[0][1]=0;     c[0][2]=0;      c[0][3]=0;
    c[1][0]=y*y; c[1][1]=0;     c[1][2]=0;      c[1][3]=y*y;
    c[2][0]=2*x*y;c[2][1]=0;     c[2][2]=y;      c[2][3]=2*x*y;
    c[3][0]=x*x; c[3][1]=1;     c[3][2]=x;      c[3][3]=x*x;
    for (int i=0;i<4;i++)
      for (int j=0;j<4;j++)
        c[i][j]%=mod;
}

void make(__int64 k){
    if (k==1){
        memcpy(p,c,sizeof(p));
        return;
    }
    make(k/2);
    memset(t,0,sizeof(t));
    for (__int64 i=0;i<4;i++)
      for (__int64 j=0;j<4;j++)
        for (__int64 k=0;k<4;k++)
          t[i][j]=(t[i][j]+p[i][k]*p[k][j])%mod;
    memcpy(p,t,sizeof(t));
    if (k&1){
        memset(t,0,sizeof(t));
        for (__int64 i=0;i<4;i++)
          for (__int64 j=0;j<4;j++)
            for (__int64 k=0;k<4;k++)
              t[i][j]=(t[i][j]+p[i][k]*c[k][j])%mod;
        memcpy(p,t,sizeof(t));
    }
}

int main(){
    while (scanf("%I64d%I64d%I64d",&n,&x,&y)!=EOF){
        if (n==1){
            printf("2n");
            continue;
        }
        if (n==0){
            printf("1n");
            continue;
        }
        n–;
        init();
        make(n);
        memset(t,0,sizeof(t));
        for (__int64 i=0;i<1;i++)
          for (__int64 j=0;j<4;j++)
            for (__int64 k=0;k<4;k++)
              t[i][j]=(t[i][j]+a[i][k]*p[k][j])%mod;
        printf("%I64dn",t[0][0]);
    }
}

[POJ 3420]状态压缩动态规划、矩阵乘法、快速幂

【题目大意】给定一个4*N的方格，求用2*1或1*2的方块把它填满有多少种方案。

【算法分析】就是用状态压缩动态规划的转移方程构造矩阵，从而用快速幂解决。

【其它】1CE,g++不允许不打stdio.h就用scanf

6418763 edward2 3420 Accepted 168K 47MS C++ 1622B 2010-02-06 21:19:33

【CODE】

#include