题解 - Vijos

1

今夜请你停驻 LV 8 @ 2012-08-02 15:56:43

题目要求的是最少渡河次数，我直接用的BFS，除了最后一个点119ms以外别的都是0ms过的，大概数据规模不大吧~

——————————————————————————————

思路是将题目叙述的信息抽象成易于表示处理的数据，每一种人、狗分布情况（指在河的哪一侧）作为一个结点，然后判断两种状态能否转移，作为两点是否联通的依据，最后采用BFS求出最短路，下面具体说我怎么处理的：

——————————————————————————————

将狗和人分别编号为0，1，2……（题目编号了狗，这里把人编为0号）然后采用二进制表达当前状态，比如可以设人和狗在起点岸记作0，在对岸记作1，这样样例中的初始状态可以表示为000000，末状态可以表示为111111，人带着狗2狗3过河之后的状态为001101（注意右边为0位置）

接下来是怎么构造可以转移的状态，也就是BFS的时候扩展哪些结点（即某种过河方案是否合法）

显然人必须过河，狗不会开船的嘛= =所以末位一定要取反（使用位运算x^=1可以取反末位，但是这里着重强调构造可行方案），这也就是说，我们需要判定的是除了最后一位以外的其他位数。

可以预见，在BFS中判断会产生大量重复计算，所以要进行预处理：哪一种状态是可行的（在人不在的情况下），这里假设人在对岸，那么就要舍弃所有在起点岸冲突的方案（检查0是否冲突），既然已经使用二进制表示那么直接枚举子集，然后对每种情况判断每种是否狗会打架（复杂度O(K * 2^N)，是指数时间的算法，但是N非常小，情况总数才1000多种，所以这里是可以容忍的）

单开一个数组储存预处理的结果（比如valid[i]储存i的二进制表示是否可行），之后进行BFS，若BFS结束仍未找到答案则输出-1

BFS的实现不难，重点在于如何判断结点是否可以扩展，首先判断渡河后人在哪岸（1&(1^x)获取末位值），若在对岸则只能保留valid[i]为真的i值，若不是则保留i取反后valid[i]为真的值

接下需要渡河人、狗总数不大于M，用当前状态和目标状态取异或，然后统计1的个数（这里可以枚举……也有高端的二分思想代码，不过我没看懂。。。感兴趣的自行Google二进制中统计1的个数[可以参见M67的位运算系列]）

最后要判断是不是过河的狗跟人在同一侧，这点十分重要不要忘记，否则答案会小于正确答案[船不能做点对点传送这种魔法的]！

———————————————————————————————

大体思路就是这样，注意细节不要写错，千万注意位运算的优先级和结合性，没把握的多加括号，然后认真调试就能AC

另外注意如果采用输出中间变量的方法调试，会发现我的算法给出的答案（样例数据）和题目背景中解法不一样，但是经过检验都是对的，所以这个没关系

———————————————————————————————

也许这个方法时间复杂度上不是最好的，但是思路比较简单，易于实现

另外无限BS之前做这道题的所有人没有一个留下过一个能看的题解粘代码粘AC结果的……什么意思嘛炫耀你AC了还是怎么着不知道一般人写的代码可读性都非常差吗一句注释都没有谁有兴趣一点点看啊！虽然SC2的配置文件也没注释但是变量名至少是有意义的单词嘛（虽然这种作风还是很恶劣。。）

最后可能细节实现上我没提但是相信都能解决的。

0

zxc123321 LV 7 @ 2018-02-12 22:03:00

//BFS的代码
#include<cstdio>
int jud[1024][2];//判重
int m,n,k;
struct river
{
int a,b;
}fit[51];
int ans;
int goal;
int yes;
int x,now,nstep;
struct river2
{
int dog,h,step;//h is human
}que[2049];
int way[1025],no;//最终打包好的状态集合;
int wayy[11];//临时装找出的二进制的集合；
int head,tail;
void m_g()//算出目标
{
int a=1,i;
for(i=1;i<=n;i++){goal+=a;a*=2;}
}
void m_p()//打包
{
int strd=1;
int i;
no++;
for(i=1;i<=n;i++)
{
way[no]=way[no]+wayy[i]*strd;
strd*=2;
}
}
void m_w(int dep)//找状态；
{
if(dep==n+1)
{
m_p();
return;
}
wayy[dep]=0;
m_w(dep+1);
wayy[dep]=1;
m_w(dep+1);
}
bool can()
{
int i,t1,t2;
for(i=1;i<=k;i++)
{
t1=x>>(fit[i].a-1)&1;
t2=x>>(fit[i].b-1)&1;
if(t1==t2&&t2==now)
return false;
}
return true;
}
int cnt(int num)
{

int count=0;

while(num)

{

count++;

num=num&(num-1);

}

return count;

}
int usex,a;
bool judge1()
{
int no=0;
while(a!=0||usex!=0)
{
int t1=a%2;int t2=usex%2;
if(t1==1&&t2==0)
return false;
if(t1==0&&t2==1)
no++;
a=a/2;usex=usex/2;
}
if(no>m)
return false;
return true;
}
bool judge2()
{
int no=0;
while(a!=0||usex!=0)
{
int t1=a%2;int t2=usex%2;
if(t1==1&&t2==0)
no++;
if(t1==0&&t2==1)
return false;
a=a/2;usex=usex/2;
}
if(no>=m)
return false;
return true;
}
void bfs()
{
que[1].dog=0;que[1].h=0;que[1].step=0;
head=0;tail=1;
int i,j;
while(head<tail)
{
head++;
x=que[head].dog;
now=que[head].h;
nstep=que[head].step;
int oldx=x;
for(i=1;i<=no;i++)
{
usex=x;a=way[i];
if(now==1)//比较
{
if(judge1())
x=way[i];
else continue;
}
if(now==0)
{
if(judge2())
x=way[i];
else continue;
}
int nnow;
if(now==1)
nnow=0;
else nnow=1;
if(jud[x][nnow]==0&&can())
{
jud[x][nnow]=1;
tail++;
que[tail].dog=x;
if(now==1) que[tail].h=0;
else que[tail].h=1;
que[tail].step=nstep+1;
if(que[tail].dog==goal)
{
if(que[tail].h==1){ans=que[tail].step;yes=1;return;}
else{ans=que[tail].step+1;yes=1;return;}
}
}
x=oldx;
}
}
}
int main()
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
scanf("%d%d%d",&m,&n,&k);
int i;
for(i=1;i<=k;i++)
scanf("%d%d",&fit[i].a,&fit[i].b);
m_g();
m_w(1);
jud[0][0]=1;
bfs();
if(yes==1)
printf("%d",ans);
else printf("-1");
return 0;
}

0

chronix LV 8 @ 2016-09-05 19:27:21

思路：
位运算储存状态+SPFA，以状态为节点。
二进制的第一位存人的状态
预处理得出那个状态可行 acc[]
访问相连状态时，判断1.acc 2.座位 3.过河的狗和人是否在同一边
注意！！！！！！
define 加括号位运算加括号
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 99999999
#define add(A,K) A|=(1<<K)
#define exist(A,K) ((A&(1<<K))!=0)
int n,m,k,end,acc[3000],AG[20]={0};

std::queue<int> q;
int inque[3000]={0};
int dist[3000];

void spfa(int u){
for(int i=0;i<=2050;i++)
dist[i]=INF;
dist[0]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
for(int i=1;i<=end;i++){
if(acc[i]==0||exist(t,0)==exist(i,0))
continue;
int chg=t^i,cnt=0,f=1,temp=i;
temp>>=1,chg>>=1;
while(chg){
if(chg&1){
f*=exist(temp,0)==exist(i,0);
cnt++;
}
chg>>=1,temp>>=1;
}
if(f&&(cnt<=m-1)){
if(dist[t]+1<dist[i]){
dist[i]=dist[t]+1;
if(!inque[i]){
q.push(i);
inque[i]=1;
}
}
}
}
}
}

int main(){
freopen("in.txt","r",stdin);
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=k;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
add(AG[t1],t2);
add(AG[t2],t1);
}
end=(1<<(n+1))-1;
for(int i=1;i<=end;i++){
int flag=1;
for(int j=1;j<=n;j++){
if((i&1)!=exist(i,j)){
//这条狗没有人管
if((i&1)==0)
flag*=(AG[j]&i)==0;
else
flag*=(AG[j]&(~i))==0;
}
}

acc[i]=flag;
}
spfa(0);
if(dist[end]==INF)
printf("-1");
else
printf("%d",dist[end]);
return 0;
}

0

Marcha LV 7 @ 2016-05-15 22:48:03

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include <stdlib.h>
#include <cmath>
#define maxn 15
#define maxm 15
#define maxk 60
#define inf 99999999
#define maxup (1<<(maxn+1))+55
using namespace std;
struct node{int t;};
queue<int> que;
vector<node> map[maxup];
int N,M,K,dist[maxup],vis[maxup]={0},upper;
bool useful[maxup];
int swp(int *a,int *b){int tmp=*a;*a=*b,*b=tmp;}
int Max(int a,int b){if(a>b) return a;return b;}
int len(int T){//取二进制数长度
    int k=0;
    while(T!=0) T>>=1,k++;
    return k;
}
int getnum(int T){//取二进制数中1的个数
    T=(T&0x55555555)+((T>>1) &0x55555555),T=(T&0x33333333)+((T>>2) &0x33333333); 
    T=(T&0x0f0f0f0f)+((T>>4) &0x0f0f0f0f),T=(T&0x00ff00ff)+((T>>8) &0x00ff00ff);
    T=(T&0x0000ffff)+((T>>16) &0x0000ffff);return T; 
}
void spfa(int T){
    dist[T]=0;que.push(T);
    while(!que.empty()){
        T=que.front();que.pop();
        for(int i=0;i<map[T].size();i++){
            if(dist[map[T][i].t]>dist[T]+1){
                dist[map[T][i].t]=dist[T]+1;
                if(vis[map[T][i].t]==0){
                    que.push(map[T][i].t);
                    vis[map[T][i].t]=1;
                }
            }
        }
        vis[T]=0;
    }
}
int judmov(int f,int t){
    int a,b,c,d;
    if((t&1)==1) swp(&f,&t);
    if(useful[f-(f^t)] && getnum((f^t)&t)<=M){
        a=f,b=t;
        for(int i=1;i<=Max(len(f),len(t));i++){
            c=a&1,d=b&1;
            if(c==0&&d==1) return 0;
            a>>=1,b>>=1;
        }
        return 1;
    }
    return 0;
}
int main(){
    int f,t,o;
    node tmp;
    cin>>M>>N>>K;
    upper=(1<<(N+1))-1;
    for(int i=0;i<=upper;i++) useful[i]=1;
    for(int i=1;i<=K;i++){
        cin>>f>>t;
        o=(1<<f)|(1<<t);
        for(int j=0;j<=upper;j++)
            if(useful[j]==1)
                if(((j&o)==o) &&  ((j&1)==0)){ useful[j]=0; useful[upper-j]=0;}
    }//read
    for(int i=0;i<=upper;i++)
        for(int j=i+1;j<=upper;j++)
            if(useful[i] && useful[j] && getnum(i^j)<=M && ((i^j)&1)==1 && judmov(i,j)){
                tmp.t=i; map[j].push_back(tmp);
                tmp.t=j; map[i].push_back(tmp);
            }//建图
    for(int i=0;i<=upper;i++) dist[i]=inf;
    spfa(0);
    printf("%d\n",dist[upper]);
}

0

Marcha LV 7 @ 2016-05-15 22:47:02

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include <stdlib.h>
#include <cmath>
#define maxn 15
#define maxm 15
#define maxk 60
#define inf 99999999
#define maxup (1<<(maxn+1))+55
using namespace std;
struct node{int t;};
queue<int> que;
vector<node> map[maxup];
int N,M,K,dist[maxup],vis[maxup]={0},upper;
bool useful[maxup];
int swp(int *a,int *b){int tmp=*a;*a=*b,*b=tmp;}
int Max(int a,int b){if(a>b) return a;return b;}
int len(int T){//取二进制数长度
int k=0;
while(T!=0) T>>=1,k++;
return k;
}
int getnum(int T){//取二进制数中1的个数
T=(T&0x55555555)+((T>>1) &0x55555555),T=(T&0x33333333)+((T>>2) &0x33333333);
T=(T&0x0f0f0f0f)+((T>>4) &0x0f0f0f0f),T=(T&0x00ff00ff)+((T>>8) &0x00ff00ff);
T=(T&0x0000ffff)+((T>>16) &0x0000ffff);return T;
}
void spfa(int T){
dist[T]=0;que.push(T);
while(!que.empty()){
T=que.front();que.pop();
for(int i=0;i<map[T].size();i++){
if(dist[map[T][i].t]>dist[T]+1){
dist[map[T][i].t]=dist[T]+1;
if(vis[map[T][i].t]==0){
que.push(map[T][i].t);
vis[map[T][i].t]=1;
}
}
}
vis[T]=0;
}
}
int judmov(int f,int t){
int a,b,c,d;
if((t&1)==1) swp(&f,&t);
if(useful[f-(f^t)] && getnum((f^t)&t)<=M){
a=f,b=t;
for(int i=1;i<=Max(len(f),len(t));i++){
c=a&1,d=b&1;
if(c==0&&d==1) return 0;
a>>=1,b>>=1;
}
return 1;
}
return 0;
}
int main(){
int f,t,o;
node tmp;
cin>>M>>N>>K;
upper=(1<<(N+1))-1;
for(int i=0;i<=upper;i++) useful[i]=1;
for(int i=1;i<=K;i++){
cin>>f>>t;
o=(1<<f)|(1<<t);
for(int j=0;j<=upper;j++)
if(useful[j]==1)
if(((j&o)==o) && ((j&1)==0)){ useful[j]=0; useful[upper-j]=0;}
}//read
for(int i=0;i<=upper;i++)
for(int j=i+1;j<=upper;j++)
if(useful[i] && useful[j] && getnum(i^j)<=M && ((i^j)&1)==1 && judmov(i,j)){
tmp.t=i; map[j].push_back(tmp);
tmp.t=j; map[i].push_back(tmp);
}//建图
for(int i=0;i<=upper;i++) dist[i]=inf;
spfa(0);
printf("%d\n",dist[upper]);
}

0

hyl LV 10 @ 2013-04-05 21:24:29

假设成立!!!

0

hyl LV 10 @ 2013-04-05 21:24:16

结果：：：
测试数据 #0: WrongAnswer, time = 7 ms, mem = 728 KiB, score = 0
测试数据 #1: WrongAnswer, time = 7 ms, mem = 728 KiB, score = 0
测试数据 #2: WrongAnswer, time = 15 ms, mem = 728 KiB, score = 0
测试数据 #3: WrongAnswer, time = 15 ms, mem = 728 KiB, score = 0
测试数据 #4: WrongAnswer, time = 15 ms, mem = 724 KiB, score = 0
测试数据 #5: WrongAnswer, time = 15 ms, mem = 724 KiB, score = 0
测试数据 #6: WrongAnswer, time = 15 ms, mem = 728 KiB, score = 0
测试数据 #7: WrongAnswer, time = 15 ms, mem = 724 KiB, score = 0
测试数据 #8: WrongAnswer, time = 11 ms, mem = 728 KiB, score = 0
测试数据 #9: WrongAnswer, time = 15 ms, mem = 728 KiB, score = 0
Summary: WrongAnswer, time = 130 ms, mem = 728 KiB, score = 0

0

hyl LV 10 @ 2013-04-05 21:23:55

证明：没有-1数据
解：提交以下程序
program lk;
begin
writeln(-1);//or writeln('-1');
end.

0

dxtdxt LV 8 @ 2010-04-05 10:47:55

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：119ms

program temp;

var

i,j,min,m,n,k,s,t,w,c,x,y,p,cc:longint;

a:array [1..2048] of longint;

b:array [0..2047] of boolean;

map:array [1..2048,1..2048] of 0..1;

dist:array [1..2048] of longint;

f:array [1..2048] of boolean;

begin

readln(m);

readln(n);

readln(k);

fillchar(b,sizeof(b),true);

p:=1 shl (n+1)-1;

for i:=1 to k do begin

readln(x,y);

c:=(1 shl x) or (1 shl y);

for j:=0 to p do begin

if ((j and c = c) and (j and 1 1)) then b[j]:=false;

if (((p-j) and c = c) and ((p-j) and 1 1 )) then b[j]:=false;

end;

end;

c:=0;

for i:=0 to p do if b[i] then begin

inc(c);

a[c]:=i;

end;

t:=c;

for i:=1 to t do

for j:=1 to t do begin

s:=0;

x:=a[i];

y:=a[j];

c:=(x and 1)-(y and 1);

inc(s);

if c=0 then s:=100000;

for k:=1 to 10 do begin

x:=x shr 1;

y:=y shr 1;

cc:=(x and 1)-(y and 1);

if cc0 then inc(s);

if cc+c=0 then begin

s:=100000;

break;

end;

end;

if s

0

jacklv LV 10 @ 2009-11-09 16:13:12

直接暴力

f 岸状态和船状态，再加些剪枝

0

notblack LV 10 @ 2009-10-27 19:53:42

第一次玩这个，艰难啊。

我原来还想枚举所有情况构图再SPFA，结果悲剧地编乱了，唉BFS之~

0

明慧 LV 10 @ 2009-10-18 15:58:47

秒杀~~~~~~~~~~~~

1次ac

水题万岁~~~~~~~~~~~~~~~~~~~~~~

program vijos_1578;

var

n,m,k : longint;

map : array[0..20,0..20]of integer;

check : array[0..4096]of boolean;

vis : array[0..1,0..4096]of boolean;

a : array[0..100000]of record

dog1,dog2,peo:integer;

end;

num,b : array[0..4096]of integer;

//======================================================

procedure init;

var

i,x,y : longint;

begin

readln(m);

readln(n);

readln(k);

fillchar(map,sizeof(map),0);

for i:=1 to k do

begin

readln(x,y);

map[x,y]:=1;

map[y,x]:=1;

end;

end;

//============================================================

procedure pre;

var

i,j,k,l,tot,sum : integer;

flag : boolean;

c : array[0..11]of integer;

begin

fillchar(check,sizeof(check),false);

for i:=0 to 1 shl n-1 do

begin

tot:=0;

sum:=0;

k:=i;

while k0 do

begin

inc(tot);

if k mod 2=1 then begin inc(sum);c[sum]:=tot;end;

k:=k div 2;

end;

flag:=true;

for l:=1 to sum do

for j:=1 to sum do

if map[c[l],c[j]]=1 then

begin

flag:=false;

break;

end;

if flag then check[i]:=true;

num[i]:=sum;

end;

end;

//==========================================================

procedure work;

var

head ,tail : longint;

i : longint;

flag : boolean;

begin

fillchar(vis,sizeof(vis),false);

head:=0;

tail:=1;

a[1].dog1:=1 shl n -1;

a[1].dog2:=0;

a[1].peo:=0;

fillchar(b,sizeof(b),0);

vis[a[1].peo,a[1].dog1]:=true;

flag:=false;

while (not flag)and(head

0

天涯残影 LV 8 @ 2009-10-05 14:33:23

Flag 　　Accepted

题号　　P1578

类型(?) 　　最短路

通过　　30人

提交　　105次

通过率　　29%

难度　　2

0

yzl609271536 LV 10 @ 2009-10-03 15:23:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC 秒杀

0

mymymy LV 10 @ 2009-08-29 12:50:46

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：166ms

调了两个小时,编了98行终于AC,可惜没秒杀......

二进制表示状态+BFS

0

zsy90943 LV 10 @ 2009-08-23 00:02:43

位压、

ORZ voyagec2神牛、

SPFA队列开了2个记录数组

v[i].x记录该岸的状态、v[i].y记录人在哪个岸(分为0，1岸)

预处理人不在时候所有可能的状态、

做s=[1 shl n-1,0],t=[1 shl n-1,1]的最短路、

PS:人在的那岸无视狗的敌对额、、

无视魔免啊、、BKB也扛不住、、

0

SDreaming LV 10 @ 2009-08-21 16:41:11

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

cjl115 LV 10 @ 2009-07-19 16:50:16

第一次写位运算

庆祝1A

Accepted 有效得分：100 有效耗时：0ms

0

voyagec2 LV 10 @ 2009-07-19 14:21:51

位压的快感

0

青鸟同学 LV 7 @ 2009-07-18 21:25:34

狼羊人

和这个差不多吧。。

题解

30 条题解

渡河

信息

状态

开发

支持

题解

30 条题解

渡河

信息

状态

开发

支持

还没有账户？

登录