博弈论——取石子问题(转)

2010年9月06日 22:46

转自 http://hi.baidu.com/alpc__ak47/blog/item/033eca25ecceaa3ac9955965.html

评论(0) 阅读(1820)

hdu 2256

2010年9月06日 05:12

一道比较难想的数学题+矩阵乘法题,这个题Jesful同学迅速AC真是犀利啊,首先题目是求floor((sqrt(2)+sqrt(3))^(2*n))就是求floor((5+2*sqrt(6))^n),考虑(5+2*sqrt(6))^n最后等于a+b*sqrt(6)那么(5-2*sqrt(6))^n就应该等于a-b*sqrt(6),所以有(5+2*sqrt(6))^n+(5-2*sqrt(6))^n=2*a,然后可以观察到(5-2*sqrt(6))^n远小于1 所以floor((5+2*sqrt(6))^n+(5-2*sqrt(6))^n)=2*a,也就是说floor((5+2*sqrt(6))^n)=2*a-1,所以只需求得a即可,求a的话就是用递推,即是说构造矩阵用矩阵乘法解决,这样时间复杂度为O(logn)----wr大牛

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct mat{int a11,a12,a21,a22;};
mat m[31];
int a,b;

void init()
{
    m[0].a11=5; m[0].a12=2;
    m[0].a21=12;m[0].a22=5;
    for(int i=1;i<=30;i++)
    {
        m[i].a11=(m[i-1].a11*m[i-1].a11+m[i-1].a12*m[i-1].a21)%1024;
        m[i].a12=(m[i-1].a11*m[i-1].a12+m[i-1].a12*m[i-1].a22)%1024;
        m[i].a21=(m[i-1].a21*m[i-1].a11+m[i-1].a22*m[i-1].a21)%1024;
        m[i].a22=(m[i-1].a21*m[i-1].a12+m[i-1].a22*m[i-1].a22)%1024;
    }
}

void modexp(int n)
{
    a=1,b=0;
    int oa,ob;
    for(int i=0;i<=30&&n;i++)
    {
        if(n&1<<i)
        {
            oa=a;ob=b;
            a=(oa*m[i].a11+ob*m[i].a21)%1024;
            b=(oa*m[i].a12+ob*m[i].a22)%1024;
            n-=1<<i;
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    init();
    int cas,n;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        modexp(n);
        printf("%d\n",(a+a+1024-1)%1024);
    }
}

评论(0) 阅读(1469)

hdu 3416 最短路+最大流

2010年9月06日 04:04

求源点到终点的不共享边的最短路有多少条.

先求一次单源最短路,得到距离数组d,考虑某条边,它的起点是k1,终点是k2,边的权是c,如果d[k2]-d[k1]=c就说明这条边是最短路上的---wr大牛

原来我的想法是求一次单源最短路得到最短路长度,然后再一次求一次单源最短路并回溯来构造流网络,实在是太菜了而且流网络方面也没有想清楚......

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct Edge{int w,wt,next;}e[1000000];
int start[maxn];
int d[maxn];//单源距离

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++)
        d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int flow[maxn][maxn],maxflow[maxn],father[maxn];
int Maxflow,visit[maxn];

void ford_fulkerson(int s,int t)
{
    queue<int>Q;
    int i,u,v;
    while(1)
    {
        //memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0
        //memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列
        for(i=0;i<n;i++) maxflow[i]=visit[i]=0;
        maxflow[s]=inf;//源点的容量置为正无穷
        Q.push(s);// 将源点压入队列
        while(!Q.empty())
        {
            u=Q.front();
            Q.pop();
            for(v=0;v<n;v++) if(!visit[v]&&flow[u][v]>0)
            {
                visit[v]=1;
                father[v]=u;//记录下他的父亲方便往后的正反向更新
                Q.push(v);
                maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者
            }
            if(maxflow[t]>0)//如果找到了汇点并且汇点容量不为0则清空队列
            {
                while(!Q.empty())
                    Q.pop();
                break;
            }
        }
        if(maxflow[t]==0)//已经找不到到汇点的增广路经了,就退出整个循环
            break;
        for(i=t;i!=s;i=father[i])
        {
            flow[father[i]][i]-=maxflow[t];//正向更新
            flow[i][father[i]]+=maxflow[t];//反向更新
        }
        Maxflow+=maxflow[t];//更新最大流
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif

    int i,v,w,wt,s,t,cnt;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        cnt=0; for(v=0;v<n;v++) start[v]=-1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&v,&w,&wt);
            v--;w--;
            e[cnt].w=w;e[cnt].wt=wt;
            e[cnt].next=start[v];start[v]=cnt++;
        }
        scanf("%d%d",&s,&t);
        s--;t--;
        spfa(s);

        //for(v=0;v<n;v++)
                //cout<<v<<":"<<d[v]<<" ";
        //cout<<endl;

        Maxflow=0;
        for(v=0;v<n;v++) for(w=0;w<n;w++) flow[v][w]=0;
        for(v=0;v<n;v++)
            for(i=start[v];i!=-1;i=e[i].next)
            {
                w=e[i].w;
                if(d[w]-d[v]==e[i].wt)
                    flow[v][w]+=1;
            }
        ford_fulkerson(s,t);
        printf("%d\n",Maxflow);
    }
}

评论(1) 阅读(2413)

poj 2186 强连通分支

2010年9月05日 01:34

tarjan 485MS

原理: 在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。
定义dfn(u)为节点u的时间戳,low(u)为节点u或u的子树能追溯到的最小的栈中节点的dfn值。当dfs回溯时发现dfn(u)==low(u),则u是分量子树的根,从u到栈顶为一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef vector<int>::iterator it;
#define maxn 10001
int inline min(int a,int b){return a<b?a:b;}
vector<int> g[maxn];
int dfn[maxn],low[maxn],stack[maxn];
int idx,top;
bool instack[maxn];
int sc,f[maxn],cnt[maxn];

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    stack[top++]=u; instack[u]=1;
    for(it v=g[u].begin();v!=g[u].end();++v)
        if(!dfn[*v])//not visited
            tarjan(*v),low[u]=min(low[u],low[*v]);
        else if(instack[*v])
            low[u]=min(low[u],dfn[*v]);
    if(dfn[u]==low[u])//find root
    {
        ++sc;cnt[sc]=0;
        do { f[stack[--top]]=sc; cnt[sc]++;
            instack[stack[top]]=0; 
        } while(u!=stack[top]);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    idx=top=sc=0;
    memset(dfn,0,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    //for(int i=1;i<=n;i++) printf("%d ",f[i]);

    //缩点
    int out[sc+1];memset(out,0,sizeof(out));
    for(u=1;u<=n;u++)
        for(it v=g[u].begin();v!=g[u].end();++v)
            if(f[u]!=f[*v]) out[f[u]]++;
    int count=0,ans;
    for(int i=1;i<=sc && count<2;i++)
        if(out[i]==0) count++,ans=i;
    if(count==1) printf("%d\n",cnt[ans]);
    else puts("0");
}

kosaraju 360MS

步骤:
1. dfs原图得到拓扑序。
2. 按照拓扑序dfs反图,每个dfs树中的顶点都是一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn],gr[maxn];
int t,gs[maxn];//toposort of g
int fs,f[maxn];//result of SCC
bool vit[maxn];

void dfs(int v)
{
    vit[v]=true;
    for(it w=g[v].begin();w!=g[v].end();++w)
        if(!vit[*w]) dfs(*w);
    gs[t--]=v;//记录拓扑顺序(finish时间的反序)
}

void rdfs(int v)
{
    vit[v]=true; f[v]=fs;
    for(it w=gr[v].begin();w!=gr[v].end();++w)
        if(!vit[*w]) rdfs(*w);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        g[i].clear(), gr[i].clear();
    while(m--)
    {
        scanf("%d%d",&v,&w);
        g[v].push_back(w);
        gr[w].push_back(v);
    }
    //正向
    memset(vit,false,sizeof(vit));
    t=n;
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
    //拓扑序
    //for(int i=1;i<=n;i++)
        //printf("%d ",gs[i]);
    //puts("");
    //逆向
    memset(vit,false,sizeof(vit));
    fs=0;
    for(int i=1;i<=n;i++)//拓扑序遍历反图
        if(!vit[gs[i]]) ++fs, rdfs(gs[i]);
    //输出每个点所属的强联通号 1~fs
    //for(int i=1;i<=n;i++)
        //printf("%d ",f[i]);

    //for poj 2186 缩点
    int out[fs+1],num[fs+1];
    memset(out,0,sizeof(out));
    memset(num,0,sizeof(num));
    for(int v=1;v<=n;v++)
    {
        num[f[v]]++;
        for(it w=g[v].begin();w!=g[v].end();++w)
            if(f[v]!=f[*w]) out[f[v]]++;
    }
    int cnt=0,ans;
    for(int i=1;i<=fs && cnt<2;i++)
        if(out[i]==0) cnt++,ans=i;
    if(cnt==1) printf("%d\n",num[ans]);
    else puts("0");
}

gabow 532MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#define maxn 10001
using namespace std;
int n,m;
vector<int> g[maxn];
int pre[maxn],path[maxn],sc[maxn],s[maxn],ct[maxn];
int cnt0,cnt1,p,top;
bool outis0[maxn];

void scDfs(int w)
{
    int v,i;
    pre[w]=cnt0++;
    s[top++]=w;path[p++]=w;
    for(i=0;i<g[w].size();i++)
    {
        v=g[w][i];
        if(pre[v]==-1) scDfs(v);
        else if(sc[v]==-1)
            while(pre[path[p-1]]>pre[v]) p--;
    }
    if(path[p-1]!=w) return; else p--;
    do sc[s[--top]]=cnt1; while(s[top]!=w);
    cnt1++;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int v,w,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) g[i].clear();
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&v,&w);
        g[v-1].push_back(w-1);
    }

    p=cnt0=cnt1=top=0;
    for(int i=0;i<n;i++)
        sc[i]=pre[i]=-1;

    for(int i=0;i<n;i++)
        if(sc[i]==-1) scDfs(i);

    //缩点
    for(i=0;i<cnt1;i++) {outis0[i]=1;ct[i]=0;}
    for(i=0;i<n;i++)
    {
        ct[sc[i]]++;
        for(j=0;j<g[i].size();j++)
            if(sc[i]!=sc[g[i][j]]) outis0[sc[i]]=0;
    }
    int index,count=0;
    for(i=0;i<cnt1;i++)
        if(outis0[i]) {index=i;count++;}
    if(count==1) printf("%d\n",ct[index]);
    else printf("0\n");
    return 0;
}

 

评论(0) 阅读(1881)

poj 2135 最小费用最大流

2010年9月03日 00:00

应该可以当模板用了

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 1005
#define inf 0x3f3f3f3f
struct edge{int v,w,f,c,next;} e[50000];
int vit[maxn],dis[maxn],start[maxn],p[maxn];
int tot,n,m;
void _add(int v,int w,int f,int c)
{
    e[tot].v=v; e[tot].w=w; e[tot].f=f; e[tot].c=c;
    e[tot].next=start[v];start[v]=tot++;
}
void add(int v,int w,int f,int c)
{
    _add(v,w,f,c);
    _add(w,v,0,-c);
}
bool spfa(int s,int t,int n)//寻找费用最小的可增广路
{
    int v,w;
    queue<int> q;
    for(int i=0;i<n;i++)
    { p[i]=-1;vit[i]=0;dis[i]=inf; }
    vit[s]=1;dis[s]=0;q.push(s);
    while(!q.empty())
    {
        v=q.front();q.pop();vit[v]=0;
        for(int i=start[v];i!=-1;i=e[i].next)
            if(e[i].f)
            {
                w=e[i].w;
                if(dis[w]>dis[v]+e[i].c)
                {
                    dis[w]=dis[v]+e[i].c;
                    p[w]=i;
                    if(!vit[w]) {vit[w]=1;q.push(w);}
                }
            }
    }
    return dis[t]!=inf;
}
int cost(int s,int t,int n)
{
    int ans=0,flow=inf,i;
    while(spfa(s,t,n))
    {
        ans+=dis[t];
        for(i=p[t];i!=-1;i=p[e[i].v])//可改进量
            if(e[i].f<flow) flow=e[i].f;
        for(i=p[t];i!=-1;i=p[e[i].v])//调整
        {
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,v,w,c;
    scanf("%d%d",&n,&m);
    for(i=0;i<n+2;i++) start[i]=-1;tot=0;//初始化
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&v,&w,&c);
        add(v,w,1,c);//添加边 此题为双向边
        add(w,v,1,c);
    }
    add(0,1,2,0);add(n,n+1,2,0);//此题添加的虚拟源点汇点
    printf("%d\n",cost(0,n+1,n+2));//最小费用
    return 0;
}

评论(0) 阅读(3207)