2015.2.9 下午进行 UVa11624 UVa10047 UVa10054 三题 图论测试
2015.2.9 晚上进行 UVa11624 UVa10047 UVa10054 三题 评测
UVa10054 订正
2015.2.10 下午进行 UVa10047 订正
2015.2.11 下午进行 La 4255 图论练习
UVa11624
题意为经典走迷宫Bfs
预处理着火的时间
从起始点进行Bfs每次到达一个点判断可行性 到终点输出即可
Const
Dx:array[1..4] of longint=(1,-1,0,0);
Dy:array[1..4] of longint=(0,0,1,-1);
Inf = 10000001;
Var
_T,H,T,Stx,Sty,n,m:longint;
V:array[0..1001,0..1001] of Boolean;
Qx,Qy:array[0..1500001] of longint;
Map,Dis,A:array[0..1001,0..1001] of longint;
Procedure Bfs2;
var x,y,_x,_y,i:longint;
begin
Fillchar(V,Sizeof(V),False);
H:=0; T:=1; Qx[1]:=Stx; Qy[1]:=Sty; V[Stx][Sty]:=True; Dis[Stx][Sty]:=1;
if (Stx=1)or(Stx=n)or(Sty=1)or(Sty=m) then begin
writeln(1);
Exit;
End;
While H<T do begin
H:=H+1;
x:=Qx[H];
y:=Qy[H];
For i:=1 to 4 do begin
_x:=x+Dx[i];
_y:=y+Dy[i];
if (_x>0)and(_x<=n)and(_y>0)and(_y<=m) then
if (A[_x][_y]=1)and(V[_x][_y]=False)and(Dis[x][y]+1<Map[_x][_y]) then begin
V[_x][_y]:=True;
T:=T+1;
Qx[T]:=_x;
Qy[T]:=_y;
Dis[_x][_y]:=Dis[x][y]+1;
if (_x=1)or(_x=n)or(_y=1)or(_y=m) then begin
writeln(Dis[_x][_y]);
Exit;
End;
End;
End;
End;
writeln('IMPOSSIBLE');
End;
Procedure Bfs1;
var x,y,_x,_y,i:longint;
begin
H:=0;
While H<T do begin
H:=H+1;
x:=Qx[H];
y:=Qy[H];
For i:=1 to 4 do begin
_x:=x+Dx[i];
_y:=y+Dy[i];
if (_x>0)and(_x<=n)and(_y>0)and(_y<=m) then
if (A[_x][_y]=1)and(V[_x][_y]=False) then begin
V[_x][_y]:=True;
Map[_x][_y]:=Map[x][y]+1;
T:=T+1;
Qx[T]:=_x;
Qy[T]:=_y;
End;
End;
End;
End;
Procedure Solve;
var i,j:longint;
C:Char;
begin
Readln(n,m);
Fillchar(V,Sizeof(V),False);
T:=0;
For i:=1 to n do begin
For j:=1 to m do begin
Read(C);
if C='#' then begin A[i][j]:=-1; Map[i][j]:=0; End;
if C='J' then begin Stx:=i; Sty:=j; End;
if (C='.')or(C='J') then begin A[i][j]:=1; Map[i][j]:=Inf; End;
if C='F' then begin T:=T+1; A[i][j]:=-1; V[i][j]:=True; Qx[T]:=i; Qy[T]:=j; Map[i][j]:=1; End;
End;
Readln;
End;
Bfs1;
Bfs2;
End;
Begin
Readln(_T);
While _T>0 do begin _T:=_T-1; Solve; End;
End.
UVa10047
拆状态表示为(x,y,u,v)的形式
其中(x,y)表示坐标 u 表示颜色 v 表示方向
用数值统一标号
Bfs/SPFA
UVa10054
欧拉回路
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define Rep(i,x,y) for (i=x;i<=y;++i)
const int n=50;
int B[300][300],N,M,m,x,y,i,Into[300],F[300*300],T,_T;
void Dfs(int u) {
int i;
Rep(i,1,n)
if (B[u][i]>0) {
--B[u][i];
--B[i][u];
Dfs(i);
}
++M;
F[M]=u;
}
void Solve() {
scanf("%d",&N);
Rep(i,1,N) {
scanf("%d%d",&x,&y);
++Into[x],++Into[y];
++B[x][y],++B[y][x];
}
m=0;
Rep(i,1,n) if (Into[i]&1) ++m;
//printf("%d\n",m);
if (m>1) { printf("some beads may be lost\n"); return; }
Dfs(1);
//printf("%d\n",M);
Rep(i,1,M-1) printf("%d %d\n",F[i],F[i+1]);
}
int main() {
scanf("%d\n",&T);
Rep(_T,1,T) {
memset(B,0,sizeof(B));
memset(Into,0,sizeof(Into));
printf("Case #%d\n",_T);
Solve();
if (i<T) printf("\n");
}
return 0;
}
想知道错在哪儿吗？...略多..
首先 if (i<T) printf("\n"); -> if (_T<T) printf("\n");
随后 if ((Into[i]&1)==1) ++m;
if (m>=1) { printf("some beads may be lost\n"); return; }
接着 Dfs(1); -> Dfs(x);
....
欧拉回路好长时间没写就忘记了 >_<
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define Rep(i,x,y) for (i=x;i<=y;++i)
const int n=50;
int B[300][300],N,m,x,y,i,Into[300],F[300*300],T,_T;
void Dfs(int u) {
int i;
Rep(i,1,n)
if (B[u][i]>0) {
--B[u][i];
--B[i][u];
Dfs(i);
printf("%d %d\n",i,u);
}
}
void Solve() {
scanf("%d",&N);
Rep(i,1,N) {
scanf("%d%d",&x,&y);
++Into[x];
++Into[y];
++B[x][y];
++B[y][x];
}
m=0;
Rep(i,1,n) if ((Into[i]&1)==1) ++m;
if (_T>1) printf("\n");
if (m>=1) { printf("Case #%d\nsome beads may be lost\n",_T); return; }
printf("Case #%d\n",_T);
Dfs(x);
}
int main() {
scanf("%d\n",&T);
Rep(_T,1,T) {
memset(B,0,sizeof(B));
memset(Into,0,sizeof(Into));
Solve();
}
return 0;
}
La 4255
显然 Ai+..Aj=S[j]-S[i-1]=T
T>0 因为均为整数 所以 T>=1
T<0 T<=-1
T=0 T>=0 T<=0
随后差分约束
因为边权为1 所以也可以拓扑排序
S[j]-S[i-1]>0 则 S[j]-S[i-1]>=1 即 j 至少要在 i-1 上 1 层
如此可以将其分层次
其为第几层答案就是几
评论 (0)
