「HRBUST1355」Leyni，罗莉和XianGe

标签：int Leyni read while HRBUST1355 虚点 XianGe dis

原题：http://222.180.160.110:1024/problem/30291

考虑建图找最短路

很容易想到以每个点作为结点，对同一行，同一列的点连边。

但是这样建图边数最大能达到 \(1e9\)

很经典的操作就是对每一行，每一列，建一个虚点。每个点都连向其对应的行、列的虚点。这样的话，就比同一行（列）的点两两连边更优。

还可以继续优化，把矩阵中的点看成图中的边。将行和列看成图中的点。所以遇到一个萝莉，就连接它的行和列两个点。

也可以这么理解：一个显然的结论是最终形态中，一个行，一个列，必定是“充满”声音的。一个萝莉相当于一个转换器，设萝莉在 \((x,y)\)，当\(x\)行充满音乐时，那么花费 \(1\) 的代价 就可以让 \(y\) 列也充满音乐。那么它可以把 行 \(x\) 转移到 列 \(y\).

\(Code\):

#include<bits/stdc++.h>
using namespace std;
int n,m;
int read(){
    int x=0;char c=getchar();bool f=0;
    while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return f?-x:x;
}
char mp[1005][1005];
const int MAXN=2e3+5;
vector<int> G[MAXN],lxx;
void Init(){
    for(int i=1;i<=n+m;i++) G[i]=lxx;
}
int dis[MAXN];
bool vis[MAXN];
const int MAX=2e9;
struct node{int to,w;};
bool operator<(const node &p,const node &q){
    return p.w>q.w;
}
void dij(int s){
    for(int i=1;i<=n+m;i++) dis[i]=MAX,vis[i]=0;
    dis[s]=0;
    priority_queue<node> q;
    q.push({s,0});
    while(!q.empty()){
        node t=q.top();q.pop();int u=t.to;
        if(vis[u])  continue;
        vis[u]=1;
        for(int v:G[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push({v,dis[v]});
            }
        }
    }
}
int main(){
    int T=read();
    while(T--){
        n=read(),m=read();
        Init();
        for(int i=1;i<=n;i++){
            scanf("%s",mp[i]+1);
            for(int j=1;j<=m;j++){
                if(mp[i][j]=='#'){
                    G[i].push_back(j+n);
                    G[j+n].push_back(i);
                }
            }
        }
        dij(1);
        if(dis[n]==MAX) printf("-1\n");
        else    printf("%d\n",dis[n]);
    }
    return 0;
}

标签：int,Leyni,read,while,HRBUST1355,虚点,XianGe,dis
From： https://www.cnblogs.com/bwartist/p/17741978.html