HDU 5961 传递

正文索引 [隐藏]

题解
代码

传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=5961

题解

满足题意，那么从每个点出发BFS，如果联通那么最短路长度<=1
每个点跑一下SPFA，判断一下就可以了。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int Maxn=2016;
struct Edge{
    int v,nxt;
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
    Edge(){};
};
int head[Maxn+5];
Edge e[Maxn*Maxn+5];
int nume;
inline void initEdge(){
    nume=0;
    memset(head,0,sizeof(head));
}
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    //e[++nume]=Edge(u,head[v]);
    //head[v]=nume;
}
int n;
int ttMap[Maxn+5][Maxn+5];
inline int read(){
    char ch=getchar();
    while(!(ch=='P' || ch=='Q' || ch=='-')) ch=getchar();
    if (ch=='P') return 1;
    if (ch=='Q') return -1;
    return 0;
}
queue<int> que;
bool inque[Maxn+5];
int dist[Maxn+5];
inline bool bfs(int src){
    while(!que.empty()) que.pop();
    memset(inque,false,sizeof(inque));
    memset(dist,-1,sizeof(dist));
    inque[src]=true;
    dist[src]=0;
    que.push(src);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            if (dist[v]==-1 || dist[v]>dist[now]+1){
                dist[v]=dist[now]+1;
                if (dist[v]>=2) return false;
                if (!inque[v]){
                    inque[v]=true;
                    que.push(v);
                }
            }
        }
        inque[now]=false;
    }
    /*printf("#%d:",src);
    for (int i=1;i<=n;i++)
        printf(" %d ",dist[i]);
    printf("\n");*/
    return true;
}
inline bool judge(int now){
    initEdge();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (ttMap[i][j]==now) addEdge(i,j);
    for (int i=1;i<=n;i++)
        if (!bfs(i)) return false;
    return true;
}
inline void solve(int T){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            ttMap[i][j]=read();
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("%d ",ttMap[i][j]);
        }
        printf("\n");
    }*/
    if (judge(1)&&judge(-1)) printf("T\n"); else printf("N\n");
}
int main(){
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve(i);
    return 0;
}

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int Maxn=2016;

struct Edge{

int v,nxt;

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

Edge(){};

};

int head[Maxn+5];

Edge e[Maxn*Maxn+5];

int nume;

inline void initEdge(){

nume=0;

memset(head,0,sizeof(head));

}

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

//e[++nume]=Edge(u,head[v]);

//head[v]=nume;

}

int n;

int ttMap[Maxn+5][Maxn+5];

inline int read(){

char ch=getchar();

while(!(ch=='P' || ch=='Q' || ch=='-')) ch=getchar();

if (ch=='P') return 1;

if (ch=='Q') return -1;

return 0;

}

queue<int> que;

bool inque[Maxn+5];

int dist[Maxn+5];

inline bool bfs(int src){

while(!que.empty()) que.pop();

memset(inque,false,sizeof(inque));

memset(dist,-1,sizeof(dist));

inque[src]=true;

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v;

if (dist[v]==-1 || dist[v]>dist[now]+1){

dist[v]=dist[now]+1;

if (dist[v]>=2) return false;

if (!inque[v]){

inque[v]=true;

que.push(v);

}

inque[now]=false;

}

/*printf("#%d:",src);

for (int i=1;i<=n;i++)

printf(" %d ",dist[i]);

printf("\n");*/

return true;

}

inline bool judge(int now){

initEdge();

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

if (ttMap[i][j]==now) addEdge(i,j);

for (int i=1;i<=n;i++)

if (!bfs(i)) return false;

return true;

}

inline void solve(int T){

scanf("%d",&n);

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

ttMap[i][j]=read();

/*for (int i=1;i<=n;i++){

for (int j=1;j<=n;j++){

printf("%d ",ttMap[i][j]);

}

printf("\n");

}*/

if (judge(1)&&judge(-1)) printf("T\n"); else printf("N\n");

}

int main(){

int T=0;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑

HDU 5961 传递

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

HDU 5961 传递

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗