注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2055  

2010-08-20 15:37:40|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目是说有k个旋钮,k个齿轮,每个旋钮控制若干个齿轮,问能否使齿轮到给定的值,若能给出一个最小总步数
就是列方程,高斯消元,然后枚举自由变量,看其他变量是否有解,由于都是整数,消元时可利用辗转相除法的思想,具体参看09年金斌的论文,这个题有些ws,不管旋钮怎么转,齿轮都是逆时针旋转,⊙﹏⊙b汗
#include<cstdio>
#include<cstring>
#define abs(a) (a<0?-(a):a)
const int inf=100000000;
int d[40][40],m,n,k,a[40][40],p[40],a1,a2,b[40],mark[40],ans;
void dfs(int pos,int sum){
if(sum>=ans)
return ;
if(pos==-1){
ans=sum;
return ;
}
if(mark[pos]!=-1){
int tmp=0;
for(int j=pos+1;j<k;++j)
tmp=((tmp+d[mark[pos]][j]*b[j])%n+n)%n;
for(int i=-n+1;i<=0;++i)
if(((tmp+i*d[mark[pos]][pos])%n+n)%n==d[mark[pos]][k]){
b[pos]=i;
dfs(pos-1,sum+abs(i));
}
}
else{
for(int i=-n+1;i<=0;++i){
b[pos]=i;
dfs(pos-1,sum+abs(i));
}
}
}
int gauss(int m,int n,int mod)
{
    int i,i0;
    for(i=0,i0=0; i<m,i0<n; ++i,++i0)
    {
        for(int j=i+1; j<m; ++j)
                while(d[j][i0]!=0)
                {
                    int t=d[i][i0]/d[j][i0];
                    for(int k=i0; k<=n; ++k)
                        d[i][k]=((d[i][k]-t*d[j][k])%mod+mod)%mod;
                    int temp;
                    for(int k=i0; k<=n; ++k)
                    {
                        temp=d[i][k];
                        d[i][k]=d[j][k];
                        d[j][k]=temp;
                    }
                }
        if(d[i][i0]==0)
        {
            --i;
            continue ;
        }
        mark[i0]=i;
    }
    for(int k=i; k<m; ++k)
        if(d[k][n])
            return 0;
dfs(m-1,0);
return 1;
}
int main(){
while(scanf("%d%d",&k,&n),k||n){
memset(mark,-1,sizeof(mark));
memset(d,0,sizeof(d));
ans=inf;
for(int i=0;i<k;++i){
scanf("%d",&d[i][k]);
--d[i][k];
}
for(int i=0;i<k;++i){
scanf("%d",&p[i]);
for(int j=0;j<p[i];++j){
scanf("%d%d",&a1,&a2);
d[a1-1][i]=a2;
}
}
if(!gauss(k,k,n)||ans==inf)
printf("No solution\n");
else printf("%d\n",ans);
}
return 0;
}
  评论这张
 
阅读(405)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017