问题模型1-1： 如果在一张图上（有向图和无向图），边权只可能是1或0，现在我们想从某个节点（假设为s）到另一个节点（假设为t），怎样才能使得路径上的权值和最大？
这是最短路径问题中的特例，因为其边权只可能是0或1；同时这也是许多问题的抽象形式，很多问题可以抽象为上述模型1-1。我们的目标就是找到一个尽可能高效的算法解决上述问题模型。
这是很容易想到的图论算法，解决此题的效率为O(NM)或O(M log N)，取决于不同的算法。
算法描述： 由于这是一张边权要么为0、要么为1的图。在这样的图上，我们可以通过双端队列广搜来计算。算法的整体框架与一般的广搜类似，只是在每个节点沿分支拓展时稍作改变。如果这条分支边权为0，则从队首入队，否则从队尾入队。这样我们能保证，任意时刻广搜队列中节点对应的距离值都有“两端性”和“单调性”，每个节点第一次被访问时，就能得到从左上角到该节点的最短距离。
效率分析： 我们可以知道该算法中每个节点仅被访问一次，因为这是BFS的特性，所以该算法的效率为O(N)。
正确性证明： 由于我们最终目标是求路径权值和，而权值为0的边无论走多少条权值和依旧是+0，因此我们可以优先走权值为0的边，更新与这些边相连的点x的d[x]（d[i] 为从s到i最小权值和），此时d[x]一定是最小的，因为它是由尽可能多的权值为0的边更新而来。所以在队列中取出的节点同时满足“连通性”和“权值最小”，因此每个节点仅需被更新一次。
电路维修 解题思路： 首先将其转化为一张边权仅由0、1构成的无向图，由于最多可能有500* 500 = 250000个点，1000，000条边，所以用此种方法时需要注意数据范围是否合适。然后就采用双端队列BFS求解，效率为O(N)，在此题中是O(R* C)。
#include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAXN = 400000; const int M = 300000*4; int head[MAXN],ver[M],Next[M],edge[M],d[MAXN]; bool vis[MAXN]; int tot,r,c,n,m; void addEdge(int x,int y,int z){ ver[++tot] = y,edge[tot] = z; Next[tot] = head[x],head[x] = tot; } void solve(){ memset(d,0x3f,sizeof d); memset(vis,false,sizeof vis); d[1] = 0; deque<int> q; q.push_back(1); while(q.size()){ int x = q.front();q.pop_front(); if(vis[x]) continue; vis[x] = true; for(int i = head[x]; i;i = Next[i]){ int y = ver[i],z = edge[i]; d[y] = min(d[x] + z,d[y]); if(z) q.push_back(y); else q.push_front(y); //printf("%d %d\n",y,d[y]); } } } void init(){ memset(head,0,sizeof head); memset(Next,0,sizeof Next); memset(ver,0,sizeof ver); tot = 0; } int main(){ int t; scanf("%d",&t); while(t--){ init(); scanf("%d%d",&n,&m); r = m+1,c = n+1; char str[MAXN]; for(int i = 0;i < n;i++){ scanf("%s",str); for(int j = 1;j <= m;j++){ if(str[j-1] == '\\'){ addEdge(i*r+j,(i+1)*r+j+1,0),addEdge((i+1)*r+j+1,i*r+j,0); addEdge((i+1)*r+j,i*r+j+1,1),addEdge(i*r+j+1,(i+1)*r+j,1); }else{ addEdge(i*r+j,(i+1)*r+j+1,1),addEdge((i+1)*r+j+1,i*r+j,1); addEdge((i+1)*r+j,i*r+j+1,0),addEdge(i*r+j+1,(i+1)*r+j,0); } } } if((n+m)%2) puts("NO SOLUTION"); else{ solve(); printf("%d\n",d[r*c]); } } return 0; }