头像

oblivion




离线:2020-02-26 04:51


活动打卡代码 AcWing 349. 黑暗城堡

oblivion
2019-09-27 05:02
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int mod=2147483647;
const int maxm=2000010;
const int maxn=100010;
struct node{
    int to;
    int next;
    int w;
}e[maxm];
int cnt,head[maxn];
void add(int u,int v,int ww){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].w=ww;
    head[u]=cnt;
}
struct point{
    int ind;
    int d;
};
bool operator <(point a,point b){
    return a.d>b.d;
}
int dis[maxn],vis[maxn];
void dij(int s){
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<point> pq;
    pq.push((point){1,0});
    dis[1]=0;
    while(!pq.empty()){
        int u=pq.top().ind;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                pq.push((point){v,dis[v]});
            }
        }
    }
}
struct opi{
    int l,r,o;
}in[maxm]; 
int ans=1;
int p[maxn];
int n,m;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&in[i].l,&in[i].r,&in[i].o);
        add(in[i].l,in[i].r,in[i].o);
        add(in[i].r,in[i].l,in[i].o); 
    }
    dij(1);
    for(int u=1;u<=n;u++){
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]==dis[u]+e[i].w){
                p[v]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(p[i]){
            ans=ans*p[i]%mod;
        }
    }
    printf("%lld\n",ans);

}


活动打卡代码 AcWing 344. 观光之旅

oblivion
2019-09-10 12:11
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
int dis[105][105];
int a[105][105];
int n,m;
int pos[105][105];
vector<int > path;
void get(int x,int y){
    if(pos[x][y]==0) return;
    get(x,pos[x][y]);
    path.push_back(pos[x][y]);
    get(pos[x][y],y);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) a[i][j]=0;
            else a[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        a[x][y]=min(z,a[x][y]);
        a[y][x]=min(z,a[y][x]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=a[i][j];
        }
    }
    int ans=inf;
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if(ans>dis[j][i]+a[i][k]+a[k][j]){
                    ans=dis[j][i]+a[i][k]+a[k][j];
                    path.clear();
                    path.push_back(i);
                    get(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    pos[i][j]=k;
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
    if(ans==inf){
        printf("No solution.\n");
    }
    else{
        for(int i=0;i<path.size();i++){
            printf("%lld ",path[i]);
        }
    }
}


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

oblivion
2019-09-10 09:50
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1000010;
const int maxm=50000010;
struct node{
    int to;
    int next;
    int w;
}e[maxm];
int head[maxn],cnt;
void add(int u,int v,int ww){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=ww;
    head[u]=cnt;
}

int n,m,k;
int dis[maxn],inq[maxn];
void spfa(){
    memset(dis,inf,sizeof(dis));
    memset(inq,0,sizeof(inq));
    inq[1]=1;
    dis[1]=0;
    queue<int >q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>max(e[i].w,dis[u])){
                dis[v]=max(e[i].w,dis[u]);
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
        for(int j=1;j<=k;j++){
            add(x+(j-1)*n,j*n+y,0);
            add(y+(j-1)*n,x+j*n,0); 
            add(x+j*n,y+j*n,z);
            add(y+j*n,x+j*n,z); 
        }
    }
    spfa();
    int maxx=inf;
    for(int j=1;j<=k+1;j++){
        maxx=min(maxx,dis[j*n]);
    }
    if(maxx==inf) printf("-1\n");
    else
    printf("%d\n",maxx);
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

oblivion
2019-09-09 13:13
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=2e5+10;
struct node{
    int to;
    int next;
    int w;
}e[maxm];
int head[maxn],cnt;
void add(int u,int v,int ww){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=ww;
    head[u]=cnt;
}
double dis[maxn];
int n,m;
int ru[maxn],du[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(y,x,z);
        du[x]++;
        ru[x]++;
    }
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            du[v]--;
            dis[v]+=(dis[u]+e[i].w)/ru[v];
            if(!du[v]){
                q.push(v);
            }
        }
    }
    printf("%.2lf\n",dis[1]);
}


活动打卡代码 AcWing 345. 牛站

oblivion
2019-09-09 12:53
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
struct node{
    int num[210][210];
}g,ans;
int cnt=0;
node operator * (node a,node b){
    node ret;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            ret.num[i][j]=inf;
            for(int k=1;k<=cnt;k++){
                ret.num[i][j]=min(ret.num[i][j],a.num[i][k]+b.num[k][j]);
            }
        }
    }
    return ret;
}

node qpow(node a,int y){
    while(y){
        if(y&1) ans=ans*a;
        a=a*a;
        y>>=1;
    }   
}
int s,e,n,m;

int to[1000010];
signed main(){
    scanf("%lld%lld",&n,&m);
    scanf("%lld%lld",&s,&e);
    for(int i=1;i<=205;i++){
        for(int j=1;j<=205;j++){
            ans.num[i][j]=inf;
            g.num[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&z,&x,&y);
        if(!to[x]){
            to[x]=++cnt;
        }
        if(!to[y]){
            to[y]=++cnt;
        }
        ans.num[to[x]][to[y]]=g.num[to[x]][to[y]]=z;
        ans.num[to[y]][to[x]]=g.num[to[y]][to[x]]=z;        
    }
    qpow(g,n-1);
    printf("%lld\n",ans.num[to[s]][to[e]]);
}




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

oblivion
2019-09-08 14:04
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f 
using namespace std;
const int maxn=100010;
const int maxm=1000000;
int n,m;
int head[maxn],cnt;
struct node{
    int to;
    int next;
}e[maxm*2];
void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
} 

int val[maxn];
struct pp{
    int x,y,z;
}in[maxm];
int dis1[maxn],dis2[maxn];
void spfa1(){
    queue<int> q;
    int inq[maxn];
    memset(dis1,inf,sizeof(dis1));
    memset(inq,0,sizeof(inq));
    dis1[1]=val[1];
    inq[1]=1;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis1[v]>min(dis1[u],val[v])){
                dis1[v]=min(dis1[u],val[v]);
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void spfa2(){
    queue<int> q;
    int inq[maxn];
    memset(dis2,0,sizeof(dis2));
    memset(inq,0,sizeof(inq));
    dis2[n]=val[n];
    inq[n]=1;
    q.push(n);
    while(q.size()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis2[v]<max(dis2[u],val[v])){
                dis2[v]=max(dis2[u],val[v]);
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&in[i].x,&in[i].y,&in[i].z);
        if(in[i].z==1){
            add(in[i].x,in[i].y);
        }
        else{
            add(in[i].x,in[i].y);
            add(in[i].y,in[i].x);           
        }
    }
    spfa1();
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++){
        if(in[i].z==1){
            add(in[i].y,in[i].x);
        }
        else{
            add(in[i].x,in[i].y);
            add(in[i].y,in[i].x);           
        }
    }
    spfa2();
    int p=0;
    for(int i=1;i<=n;i++) {
        p=max(p,dis2[i]-dis1[i]);
    }
    printf("%d\n",p);
}


活动打卡代码 AcWing 346. 走廊泼水节

oblivion
2019-09-05 09:48
#include<bits/stdc++.h>
using namespace std;
const int maxn=60010;
int fa[maxn];
int find(int x){
    if(fa[x]==x) return fa[x];
    return fa[x]=find(fa[x]);
} 
int t;
struct node{
    int x;
    int y;
    int w;
}in[maxn];
int s[maxn];
bool cmp(node a,node b){
    return a.w<b.w;
}
long long ans;
int n;
void kruskal(){
    sort(in+1,in+n,cmp);
    for(int i=1;i<n;i++){
        int eu=find(in[i].x);
        int ev=find(in[i].y);
        if(eu!=ev){
            ans+=(long long)(s[eu]*s[ev]-1)*(in[i].w+1); 
            fa[eu]=ev;
            s[ev]+=s[eu];
        }
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        ans=0;
        memset(s,0,sizeof(s));
        memset(in,0,sizeof(in));
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d%d%d",&in[i].x,&in[i].y,&in[i].w);
        }
        for(int i=1;i<=n;i++){
            fa[i]=i;
            s[i]=1;
        }
        kruskal();
        printf("%lld\n",ans);
    }   
}


活动打卡代码 AcWing 289. 环路运输

oblivion
2019-09-04 13:54
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
int n,m;
int ans[2000010];
int cnt;
int q2[2000010];
int a[2000010];
int b[2000010];
int solve(){
    int h=1,t=0;
    for(int i=1;i<=n*2;i++){
        while(h<=t && q2[h]<=i-m) h++;
        while(h<=t && b[q2[t]]<b[i]) t--;
        q2[++t]=i;
        ans[++cnt]=b[q2[h]];
    }
}
int mjc=0;
signed main(){
    cin>>n;
    m=n/2+1;
    m--;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        b[i]=a[i]-i;
    }
    solve();
    for(int i=1;i<=n*2;i++){
        mjc=max(mjc,i+a[i]+ans[i-1]);
    }
    printf("%lld\n",mjc);
    return 0; 
}


活动打卡代码 AcWing 288. 休息时间

oblivion
2019-09-04 13:38
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[4000];
int f[3][4000][3];
int ff[3][4000][3];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    memset(f,-0x3f,sizeof(f));
    memset(ff,-0x3f,sizeof(ff));
    f[1][0][0]=0;f[1][1][1]=0;
    ff[1][1][1]=a[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(i,m);j++){
            f[i%2][j][0]=max(f[(i+1)%2][j][0],f[(i+1)%2][j][1]);
            if(j>=1) f[i%2][j][1]=max(f[(i+1)%2][j-1][0],f[(i+1)%2][j-1][1]+a[i]);
            ff[i%2][j][0]=max(ff[(i+1)%2][j][0],ff[(i+1)%2][j][1]);
            if(j>=1) ff[i%2][j][1]=max(ff[(i+1)%2][j-1][0],ff[(i+1)%2][j-1][1]+a[i]);
        }
    }
    printf("%d\n",max(ff[n%2][m][1],max(f[n%2][m][0],f[n%2][m][1])));
}


活动打卡代码 AcWing 149. 荷马史诗

oblivion
2019-08-14 12:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int w;
    int h;
};

struct cmp{
    bool operator()(node a,node b){
        if(a.w==b.w) return a.h>b.h;
        return a.w>b.w;
    }
}; 

int cnt;
priority_queue<node ,vector<node> ,cmp> pq;
int w[100010];
int n,k,q;
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%lld",&t);
        node u;
        u.h=1;u.w=t;
        pq.push(u);
    }
    if((n-1)%(k-1)!=0) cnt+=k-1-(n-1)%(k-1);
    for(int i=1;i<=cnt;i++){
        node u;
        u.h=1;u.w=0;
        pq.push(u);
    }
    cnt+=n;
    while(cnt>1){
        int ans=0,maxx=0;
        for(int i=1;i<=k;i++){
            node u=pq.top();
            ans+=u.w;
            maxx=max(maxx,u.h);
            pq.pop();           
        }
        node v;
        v.h=maxx+1;
        v.w=ans;
        pq.push(v);
        q+=ans;
        cnt-=k-1;
    }
    printf("%lld\n%lld",q,pq.top().h-1);
}