bzoj2346[Baltic 2011]Lamp
Description
2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。
n,m<=500
Input
Output
Sample Input
3 5
\\/\\
\\///
/\\\\
Sample Output
1
……我是弱渣……原来以为是各种流乱搞，结果ksy学长告诉我是最短路
如果符号是“/”左下方的点向右上方的点连边权为0的边，左上方向右下方连边权为1的边
如果符号是“\”左上方的点向右下方的点连边权为0的边，左下方向右上方连边权为1的边 然后上最短路……别忘了加双向边
25w的点Dj+堆可以秒过，但是SPFA呵呵呵……不过我有特殊的优化SPFA的方法
要用SLF优化，就是更新的时候如果当前更新的dist比正在做的dist小，就把它放在队头。具体看代码，还不会的自行百度
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 127/3
#define mod 1000007
using namespace std;
struct edge{
int next,to,v;
}e;
int cnt;
int head;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;
e.v=w;
e.next=head;
head=cnt;
}
inline void insert(int u,int v,int w)
{
ins(u,v,w);
ins(v,u,w);
}
int n,m,t,w=1;
char ch;
int dist;
bool flag;
int q;
inline void spfa()
{
memset(dist,inf,sizeof(dist));
int now;q=1;dist=0;flag=1;
while (t!=w)
{
t=(t+1)%mod;
now=q;
for (int i=head;i;i=e.next)
if (dist+e.v<dist.to])
{
dist.to]=dist+e.v;
if (!flag.to])
{
if(dist>=dist.to])
{
q=e.to;
flag.to]=1;
t=(t-1+mod)%mod;
}else
{
w=(w+1)%mod;
q=e.to;
flag.to]=1;
}
}
}
flag=0;
}
}
int main()
{
scanf("%d%d",&n,&m);
if ((n+m)&1)
{
printf("NO SOLUTION");
return 0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
ch=' ';
while (ch!='/' && ch!='\\' ) scanf("%c",&ch);
if (ch=='\\')
{
insert((i-1)*(m+1)+j+1,i*(m+1)+j,1);
insert((i-1)*(m+1)+j,i*(m+1)+j+1,0);
}
else if (ch=='/')
{
insert((i-1)*(m+1)+j,i*(m+1)+j+1,1);
insert((i-1)*(m+1)+j+1,i*(m+1)+j,0);
}
}
spfa();
printf("%d\n",dist[(n+1)*(m+1)]);
}
页:
[1]