头像

little.white.4


访客:1648

离线:4小时前


活动打卡代码 AcWing 343. 排序

// 这题坑点太多,每次加入一条新边跑floyd更新答案

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 501000
using namespace std;
int n,m;
bool dis[40][40];
bool g[40][40];
bool vis[N];
void floyd(){
    memcpy(dis,g,sizeof dis);
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dis[i][j] |= (dis[i][k] && dis[k][j]);
            }

        }
    }
}

int check(){
    for(int i=0;i<n;i++){
        if(dis[i][i]) return 0; // floyd 会将有环的任意两个点变为true
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(!dis[i][j]&&!dis[j][i])return 1;
        }
    }
    return 2;
}
char  getmin(){

    for(int i=0;i<n;i++){
        if(vis[i])continue;
        bool f=true;
        for(int j=0;j<n;j++){
            if(!vis[j]&&dis[j][i]){
                f=false;
                break;
            }
        }
        if(f){
            vis[i]=1;
            return 'A'+i;
        }
    }
    return '1';
}
int main(){
    while(1){
        cin>>n>>m;
        if(!n&&!m)break;
        int  ty=1;
        memset(g,0,sizeof g);
        bool f=false;

        int cnt=1;

        for(int i=0;i<m;i++){

           char str[5];
           cin>>str;
            int x=str[0]-'A',y=str[2]-'A';
             g[x][y]=1;

            if(!ty||ty==2){// type 为0

                continue;
            }
            // 跑 floyd 

             floyd();
            //int te=ty;
             ty=check();

            if(ty==0){
                continue;
            }
            if(ty==2){
                f=true;
                continue;
            }
            cnt++;

        }
        //cout<<type<<endl;
        if(!ty){
            printf("Inconsistency found after %d relations.\n",cnt);
            continue;
        }
        if(f){
            memset(vis,0,sizeof vis);
            printf("Sorted sequence determined after %d relations: ",cnt);
            for(int i=0;i<n;i++){
                printf("%c",getmin());
            }
            printf(".\n");

        }
        else{
            printf("Sorted sequence cannot be determined.\n");
        }
    }    
    return 0;
}


活动打卡代码 AcWing 1125. 牛的旅行

#include<bits/stdc++.h>
#define N 301
#define mod 100000007
#define f first
#define s second
#define pii pair<int,int>
#define inf 0x3f3f3f3f
using namespace std;
double dis[N][N];
pii v[N];
double maxi[N];
double getdis(pii a,pii b){
    double dx=fabs(a.f-b.f),dy=fabs(a.s-b.s);
    return sqrt(dx*dx+dy*dy);
}
char g[500][500];
int main(){
    int n;
    cin>>n;

    for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s;
    for(int i=0;i<n;i++)scanf("%s",g[i]);
    // 初始化dis数组 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(g[i][j]=='1'){
                dis[i][j]=getdis(v[i],v[j]);
            }
            else{
                dis[i][j]=inf;
            }

        }
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    // 更新 maxdis 数组获取每个i 出发的直径
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dis[i][j]<inf) maxi[i]=max(maxi[i],dis[i][j]);
        }
    }
    double res1=0,res2=inf;
    for(int i=0;i<n;i++)res1=max(res1,maxi[i]);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dis[i][j]>=inf){
                res2=min(res2,getdis(v[i],v[j])+maxi[i]+maxi[j]);
            }
        }
    }
    res2=max(res1,res2);
    printf("%.6lf",res2);
    //


    return 0;
}


活动打卡代码 AcWing 1273. 天才的记忆

#include<bits/stdc++.h>
#define ll long long 
#define mod 1000000007
#define N 1001000
using namespace std;
int n,m;
int a[N];
int tree[N];
void push_up(int node){
    tree[node]=max(tree[node*2],tree[node*2+1]);
}
void build(int l, int r, int rt) {//用满二叉树建树

    if (l == r) {//叶子结点,赋值
        scanf("%d", &tree[rt]);
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    push_up(rt);//向上更新区间和
}
int query(int a, int b, int l, int r, int rt) {//区间求和
    if (a <= l && b >= r)
        return tree[rt];//满足lazy直接返回

    int mid = (l + r) >> 1;
    int ans = INT_MIN;
    if (a <= mid)ans = max(ans,query(a, b, l,mid,rt*2));
    if (b > mid)ans = max(ans,query(a, b, mid+1,r,rt*2+1));
    return ans;
}
int main(){

    cin>>n;
    build(1,n,1);
    cin>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        cout<<query(a,b,1,n,1)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 383. 观光

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 701000
using namespace std;
int e[N],ne[N],h[N],idx,w[N];
int vis[N][2],dis[N][2];
int res[N][2];


int result=0;

struct ver{
    int vec,t,w;
    bool operator>(const ver&T)const{
        return w>T.w;

    }
};
int n,m;
int S,F;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;

}
void DJ(){
    priority_queue<ver,vector<ver>,greater<ver>>q;
    memset(dis,inf,sizeof dis);
    memset(vis,0,sizeof vis);
    memset(res,0,sizeof res);
    dis[S][0]=0;
    res[S][0]=1;

    q.push({S,0,0});

    while(!q.empty()){
        int v=q.top().vec,ty=q.top().t;
        int distance=q.top().w;
        int count=res[v][ty];
        q.pop();
        if(vis[v][ty])continue;
        vis[v][ty]=1;

        for (int i = h[v]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dis[j][0] > distance + w[i])
            {
                dis[j][1] = dis[j][0], res[j][1] = res[j][0];
                q.push({j, 1, dis[j][1]});
                dis[j][0] = distance + w[i], res[j][0] = count;
                q.push({j, 0, dis[j][0]});
            }
            else if (dis[j][0] == distance + w[i]) res[j][0] += count;
            else if (dis[j][1] > distance + w[i])
            {
                dis[j][1] = distance + w[i],res[j][1] = count;
                q.push({j, 1, dis[j][1]});
            }
            else if (dis[j][1] == distance + w[i]) res[j][1] += count;
        }



    }
    result=res[F][0];
    if(dis[F][0]+1==dis[F][1])result+=res[F][1];
    cout<<result<<endl;
}
int main(){
    int t;
    cin>>t;



    while(t--){
        cin>>n>>m;
        result=0;
        idx=0;
        memset(h,-1,sizeof h);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        cin>>S>>F;

        DJ();

    }
    return 0;


}


活动打卡代码 AcWing 1134. 最短路计数

#include<bits/stdc++.h>
#define N 1001000
#define mod 100003
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define ll long long
using namespace std;
int dis[N],ne[N],e[N],w[N],h[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int vis[N];
int res[N];
int n,m;
void SPFA(){
    memset(dis,inf,sizeof dis);
    dis[1]=0;
    res[1]=1;
    queue<int>q;
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];

            if(dis[v]==dis[u]+1)res[v]=(res[v]+res[u])%mod;
            else{
                if(dis[v]>dis[u]+1)dis[v]=dis[u]+1,res[v]=res[u];
            }

            if(!vis[v]){
                q.push(v);
                vis[v]=1;
            }
        }


    }
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    SPFA();
    for(int i=1;i<=n;i++){
        if(res[i])cout<<res[i]<<endl;
        else
        cout<<0<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1137. 选择最佳线路

// 多个源点可以选择,一开始把所有源点放入队列中即可

#include<bits/stdc++.h>
#define N 501000
#define inf 0x3f3f3f3f

using namespace std;
int h[N],e[N],w[N],ne[N],idx,vis[N];
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int n,m,s,cc[N],dis[N],ww;
void SPFA(){
    memset(dis,inf,sizeof dis);
    queue<int>q;

    for(int i=1;i<=ww;i++){
        q.push(cc[i]);
        dis[cc[i]]=0;
        vis[cc[i]]=1;

    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(dis[s]==inf)cout<<-1<<endl;
    else
    cout<<dis[s]<<endl;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(h,-1,sizeof h);

        cin>>m>>s;
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);

        }


        cin>>ww;
        for(int i=1;i<=ww;i++){
            cin>>cc[i];
        }
        SPFA();
    }
    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

// 分段dp思想找出买入卖出差值最大的两个点,首先正向建图跑最短路,更新dismin ,然后反向建图更新dismax

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 2001000
using namespace std;
int vis[N],hs[N],ht[N],ne[N],e[N],w[N],idx;
int dismin[N],dismax[N];
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
void SPFA(int h[],int dis[],int f){
    queue<int>q;

    if(!f){
        memset(dis,inf,sizeof dismin);
        dis[1]=w[1];
        vis[1]=1;
        q.push(1);
    }
    else{
        memset(dis,-inf,sizeof dismax);
        dis[n]=w[n];
        vis[n]=1;
        q.push(n);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;

        if(!f){

            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];

                if(dis[v]>min(dis[u],w[v])){
                    dis[v]=min(dis[u],w[v]);
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }

            }

        }
        else{

            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];
                if(dis[v]<max(dis[u],w[v])){
                    dis[v]=max(dis[u],w[v]);
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }


        }

    }
}
int main(){
    cin>>n>>m;
    memset(hs,-1,sizeof hs);
    memset(ht,-1,sizeof ht);
    for(int i=1;i<=n;i++)cin>>w[i];
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(hs,a,b);
        add(ht,b,a);
        if(c==2){
            add(hs,b,a);
            add(ht,a,b);
        }
    }
    SPFA(hs,dismin,0);
    SPFA(ht,dismax,1);
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,dismax[i]-dismin[i]);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 342. 道路与航线

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long  long
#define N 1001000
#define inf 0x3f3f3f3f
using namespace std;
int dis[N],vis[N],w[N],e[N],ne[N],h[N],idx;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int T,R,P,S;
int fa[N];
int id[N];

int cntb;//  联通块的编号

queue<int>q;//为啥要设置全局队列

vector<int>block[N];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int in[N];// 联通块入度编号
void dfs(int x, int cnt)
{
    id[x] = cnt;
    block[cnt].push_back(x);

    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!id[j])
            dfs(j, cnt);
    }
}
void DJ(int x){//对联通块x做最短路
    priority_queue<pii,vector<pii>,greater<pii>>pq;

    for(auto &e:block[x]){
        pq.push({dis[e],e});
    }

    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
      //  cout<<u<<" ";
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            int ww=w[i];
            if(dis[v]>dis[u]+ww){
                dis[v]=dis[u]+ww;
                //cout<<v<<" ";
                if(id[v]==id[u]){
                    pq.push({dis[v],v});
                }

            }
            if(id[v]!=id[u]){
                in[id[v]]--;
                if(in[id[v]]==0)
                q.push(id[v]);
            }
        }
    }

}
void tuopu(){
    for(int i=1;i<=cntb;i++){
        if(in[i]==0)q.push(i);
    }
    memset(dis,inf,sizeof dis);
    dis[S]=0;
    while(q.size()){
        int p=q.front();
        q.pop();
        DJ(p);
    }
}
int main(){
    cin>>T>>R>>P>>S;
    memset(h,-1,sizeof h);
    for(int i=0;i<R;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    // 对双向道路的每个点做并查集
    for(int i=1;i<=T;i++){
        if(!id[i]){//如果当前点没有联通/加入并查集
        cntb++;
            dfs(i,cntb);
        }
    }
    for(int i=0;i<P;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        in[id[b]]++;// 因为是有向边,将b所在的联通块 入度++
    }
    tuopu();
    for(int i=1;i<=T;i++){
        if(dis[i]>inf/2){// 因为有负权边的存在使得到不了的点的dis  inf会减小,因此判断是否大于 inf/2
            cout<<"NO PATH"<<endl;

        }
        else
        cout<<dis[i]<<endl;
    }
    return 0;

}


活动打卡代码 AcWing 175. 电路维修

// 剖析:对于每两个点来说有两种边可以连通一种是原来的边,值为0,一种是新加的一条边,值为1,符合这种仅两个单独性质的
// 可以用双端队列
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define N 1001000
using namespace std;
int dis[N],vis[N],e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
void DJ(){
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof vis);
    deque<int>dq;
    dq.push_front(1);
    dis[1]=0;
    while(!dq.empty()){
        int u=dq.front();
        dq.pop_front();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            int ww=w[i];

            if(dis[v]>dis[u]+ww){
                dis[v]=dis[u]+ww;
                if(ww)dq.push_back(v);
                else{
                    dq.push_front(v);
                }
            }
        }
    }
    if(dis[(n+1)*(m+1)]==inf){
        cout<<"NO SOLUTION"<<endl;
        return ;
    }
    cout<<dis[(n+1)*(m+1)]<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(h,-1,sizeof h);
        memset(e,0,sizeof e);
        memset(ne,0,sizeof ne);
        memset(w,0,sizeof w);
        idx=0;
        int cnt=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char c;
                cin>>c;
                if(c=='\\'){
                    add(cnt,cnt+m+2,0);
                    add(cnt+m+2,cnt,0);
                    add(cnt+1,cnt+m+1,1);
                    add(cnt+m+1,cnt+1,1);
                }
                else{
                    add(cnt,cnt+m+2,1);
                    add(cnt+m+2,cnt,1);
                    add(cnt+1,cnt+m+1,0);
                    add(cnt+m+1,cnt+1,0);
                }

                cnt++;
            }
            cnt+=1;
        }



        DJ(); 
    }


    return 0;
}


活动打卡代码 AcWing 340. 通信线路

#include<bits/stdc++.h>
#define N 500100
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int ne[N],h[N],e[N],idx,w[N],dis[N];
int vis[N];
void add(int a,int b,int c){

    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;

}
int n,p,k;
bool check(int len){//将大于len的边权置为1,小于等于len的边权值置为0,双端队列跑bfs

    memset(dis,inf,sizeof dis);

    memset(vis,0,sizeof vis);
    dis[1]=0;
    deque<int>dq;//与堆优化的diJ一样,双端队列里面一定加点
    dq.push_front(1);

    while(!dq.empty()){
        int u=dq.front();
        dq.pop_front();
        if(vis[u])continue;
        vis[u]=1;

        for(int i=h[u];~i;i=ne[i]){                    
            int v=e[i];
            int ww=(w[i]>len);
           if(vis[v])continue;
            if(dis[v]>dis[u]+ww){
                dis[v]=dis[u]+ww;
                    if(ww){
                        dq.push_back(v);//如果边权为1,从尾巴压入
                    }
                    else{
                        dq.push_front(v);// 贪心,边权为0的必然是先进队的
                    }

            }

        }

    }

    return dis[n]<=k;
}
int main(){
    cin>>n>>p>>k;
    memset(h,-1,sizeof h);//必须初始化邻接表头
    for(int i=0;i<p;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int l=0,r=1e6+1;
    while(l<r){
        int mid= l+r >>1;
        if(check(mid))r=mid;
        else
        l=mid+1;
    }
    if(r==1e6+1)r=-1;
    cout<<r<<endl;
    return 0;
}