bzoj2346 baltic2011 lamp

bzoj2346 baltic2011 lamp

​​ Description

2255是一个傻X，他连自己家灯不亮了都不知道。 某天TZ大神路过他家，发现了这一情况， 于是TZ开始行侠仗义了。 TZ发现是电路板的问题， 他打开了电路板，发现线路根本没有连上！！ 于是他强大的脑力可以使某个格子上的线路从\变为/， 或者从/变为\。 2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。 如果无法变亮，输出“NO SOLUTION”。

n,m<=500

Input

Output

Sample Input

3 5 \/\ \/// /\\ Sample Output

1 HINT

Source

这题可能是卡普通spfa 大概我tle 了 那用slf优化下，过了的

建图的时候存在这条边则代价为0，反之为1，双向建立边

#include#include#include#include#define N 550inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int x,z,y,next;}data[4*N*N];char s[N][N];int f[N*N],h[N*N],n,m,num;bool flag[N*N];void spfa(){ std::deque q;q.push_back(1); memset(f,0x7f,sizeof(f));flag[1]=true;f[1]=0; while (!q.empty()){ int x=q.front();flag[x]=false;q.pop_front(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+z

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。