博弈论——取石子问题(转)
2010年9月06日 22:46
转自 http://hi.baidu.com/alpc__ak47/blog/item/033eca25ecceaa3ac9955965.html
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);
}
}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);
}
}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;
}
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;
}
