danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29174

[UOJ 19]寻找道路

2016年9月10日 21:35 | Comments(0) | Category:题解 | Tags:

这个题难就难在,别说重边自环,就是简单有向环,也会让DFS爆炸。所以考虑BFS。

但……BFS怎么判断其他点到[tex]t[/tex]的联通?

方法是,把边都反过来!这样BFS一遍就可以判联通了。

然后接下来BFS最短路就简单了,注意一些特判。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=10005,maxm=400005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
bool rev[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v,bool reverse=false){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
    rev[graph_tot]=reverse;
}

int s,t;
bool vis[maxn];
bool LT[maxn];
bool bfs_1(){
    register int i,u;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t]=true;
    LT[t]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        GRAPH_REP(i,u){
            if(rev[i] && !vis[to[i]]){
                LT[to[i]]=true;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return LT[s];
}

int dep[maxn];
int bfs_2(){
    register int i,u;
    bool Allow;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s]=true;
    dep[s]=0;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        Allow=true;
        GRAPH_REP(i,u){
            if(!rev[i] && !LT[to[i]]){
                Allow=false;
                break;
            }
        }
        if(!Allow)
            continue;
        GRAPH_REP(i,u){
            if(!rev[i] && !vis[to[i]]){
                dep[to[i]]=dep[u]+1;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return vis[t]?dep[t]:-1;
}

int main(){
    int n,m,u,v;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u,true);
    }
    scanf("%d%d",&s,&t);
    if(!bfs_1()){
        puts("-1");
    }else{
        printf("%d\n",bfs_2());
    }
    return 0;
}

[UOJ 16]联合权值

2016年9月10日 20:59 | Comments(0) | Category:题解 | Tags:

这个题的关键啊……就在于那个中间点。

我们可以枚举中间点,然后进行统计。

至于最大联合权值,直接找中间点相邻点中最大权值和次大权值的积的最大值。至于联合权值之和,可以推出这样一个式子([tex]x[/tex]与中间点相邻,其中[tex]s[/tex]是所有和中间点相邻的点的权值和):

[tex]\Sigma x\mul (s-x)[/tex]

这就好弄多了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2*1e5+5;
const int maxm=maxn*2,MOD=10007;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}

// int pow_mod(int a,int b){
//     if(!b){
//         return 1;
//     }
//     int x=pow_mod(a,b>>1);
//     long long ans=(((long long)x)*((long long)x))%MOD;
//     if(1&b)
//         ans=ans*(a%MOD)%MOD;
//     return (int)ans;
// }
int d[maxn];
int main(){
    int n,u,v,temp,temp2;
    register int i,j,ans1=0,ans2=0,sum,maxv,smax;
    scanf("%d",&n);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    REP(i,n){
        scanf("%d",&d[i]);
    }
    REP(i,n){
        sum=maxv=smax=0;
        GRAPH_REP(j,i){
            temp=to[j];
            sum=(d[temp]%MOD+sum)%MOD;
            if(d[temp]>maxv){
                smax=maxv;
                maxv=d[temp];
            }else{
                if(d[temp]>smax)
                    smax=d[temp];
            }
        }
        ans1=max(ans1,maxv*smax);
        temp2=0;
        GRAPH_REP(j,i){
            temp=to[j];
            temp2=(temp2+(d[temp]%MOD)*((sum-(d[temp]%MOD)+MOD)%MOD)%MOD)%MOD;
        }
        ans2=(ans2+temp2)%MOD;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}