Article From:https://www.cnblogs.com/KatouKatou/p/9684168.html

T1 repair Highway”

\(c1\)Sort, finish\(k\)Select and press\(c2\)Sort, get the maximum edge weight when building a tree.

\(code\):

#include<stdio.h>
#include<algorithm>
#include<ctype.h>
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template<typename T>
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(x=0,flag=1):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    flag?x=-x:x=x;
}

struct node {
    int u,v,c1,c2;
    inline node(int a=0,int b=0,int c=0,int d=0) {
        u=a;
        v=b;
        c1=c;
        c2=d;
    }
} a[20005];

int n,m,k,ans;
int cnt;
int fa[10005];

inline bool cmp1(node a,node b)
{
    return a.c1<b.c1;
}

inline bool cmp2(node a,node b)
{
    return a.c2<b.c2;
}

ll getfa(int x)
{
    if(x==fa[x]) return x;
    fa[x]=getfa(fa[x]);
    return fa[x];
}

int main()
{
    read(n),read(k),read(m);
    for(int i=1; i<=m; i++) {
        int x,y,c1,c2;
        read(x),read(y),read(c1),read(c2);
        a[i]=node(x,y,c1,c2);
    }
    for(int i=1; i<=n; i++) fa[i]=i;
    sort(a+1,a+1+m,cmp1);
    for(int i=1; i<=m&&cnt!=k; i++) {
        int fx=getfa(a[i].u),fy=getfa(a[i].v);
        if(fx==fy) continue;
        ans=max(ans,a[i].c1);
        fa[fx]=fy;
        cnt++;
    }
    
    sort(a+1,a+1+m,cmp2);
    for(int i=1; i<=m&&cnt!=n-1; i++) {
        int fx=getfa(a[i].u),fy=getfa(a[i].v);
        if(fx==fy) continue;
        ans=max(ans,a[i].c2);
        fa[fx]=fy;
        cnt++;
    }
    printf("%d",ans);
}

T2 [USACO 2015 Jan Gold] herbage connoisseur

1. is a one-way side, so it is easy to think of it.\(tarjan\)Shrinkage point;

3. Initialize when the final answer is counted\(Ans=size[belong[1]]\),Avoid the existence of a positive solution for the whole graph when there is only one ring.\(Ans=max(ans,(ll)(dis[i][1]+dis[p][0]))\)

\(code:\)

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
#include<ctype.h>
#include<vector>
#include<queue>
#define ll long long
#define inf 1e9+9
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template<typename T>
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    flag?x=-x:x=x;
}

struct node {
    int x,len;
    inline node(int a=0,int b=0) {
        x=a;
        len=b;
    }
    bool operator<(node a)const {
        return len<a.len;
    }
};

int n,m,tot,scc,belong[100005],sz[100005];
ll dis[100005][2];
bool instack[100005];
vector<int>G[100005];
vector<node>g[100005][2];
stack<int>s;
int low[100005],dfn[100005];
priority_queue<node>q;

void djs(int start,int t)
{
    for(int i=1; i<=scc; i++) dis[i][t]=-inf;
    dis[start][t]=(t==1)?sz[start]:0;
    q.push(node(start,dis[start][t]));
    while(!q.empty()) {
        int x=q.top().x;
        int len=q.top().len;
        q.pop();

        if(len!=dis[x][t]) continue;
        for(int i=g[x][t].size()-1; i>=0; i--) {
            int p=g[x][t][i].x;
            len=g[x][t][i].len;
            if(dis[p][t]>=dis[x][t]+len) continue;
            dis[p][t]=(ll)dis[x][t]+len;
            q.push(node(p,dis[p][t]));
        }
    }
}

void dfs(int x)
{
    low[x]=dfn[x]=++tot;
    s.push(x),instack[x]=1;
    int p;
    for(int i=G[x].size()-1; i>=0; i--) {
        int p=G[x][i];
        if(!dfn[p]) {
            dfs(p);
            low[x]=min(low[x],low[p]);
        } else if(dfn[p]&&instack[p]) {
            low[x]=min(low[x],low[p]);
        }
    }
    if(low[x]==dfn[x]) {
        scc++;
        do {
            p=s.top();
            s.pop();
            instack[p]=0;
            belong[p]=scc;
            sz[scc]++;
        } while(x!=p);
    }
}

ll ans;
int main()
{
    read(n),read(m);
    for(int i=1; i<=m; i++) {
        int x,y;
        read(x),read(y);
        G[x].push_back(y);
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) dfs(i);
    for(int i=1; i<=n; i++)
        for(int j=G[i].size()-1; j>=0; j--) {
            int p=G[i][j];
            if(belong[i]==belong[p]) continue;
            g[belong[i]][1].push_back(node(belong[p],sz[belong[p]]));
            g[belong[p]][0].push_back(node(belong[i],sz[belong[i]]));
        }

    djs(belong[1],0);
    djs(belong[1],1);

    ans=sz[belong[1]];
    int start=belong[1];
    for(int i=1; i<=scc; i++) {
        for(int j=g[i][0].size()-1; j>=0; j--) {
            int p=g[i][0][j].x;
            ans=max(ans,(ll)(dis[i][1]+dis[p][0]));
        }
    }
    printf("%lld",ans);
    return 0;
}

T3 take delivery”

state compressed + DP, and the state i s\(f[i][S]\),Presentation processing\(s\)The point in this collection stays behind.\(i\)Number point\((1<=i<=k)\),Record the restricted state U with an array, when satisfied\((S\)|\(U==S)\)When you can transfer, see the status transition.\(code\)

\(code:\)

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#define ll long long
#include<ctype.h>
#define inf 1e9+9
using namespace std;

char buf[1038576],*p1,*p2;
inline char gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1038576,stdin))==p1?0:*p1++;
}
template<typename T>
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(x=0,flag=1):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

char pbuf[1038576],*pp=pbuf;
inline void push(const char c)
{
    if(pp-pbuf==(1038576)) fwrite(pbuf,1,(1038576),stdout),pp=pbuf;
    *pp++=c;
}

template<typename T>
inline void write(T x)
{
    static int sta[35];
    int top=0;
    do {
        sta[top++]=x%10,x/=10;
    } while(x);
    while(top) push(sta[--top]+'0');
    push('\n');
}

struct node {
    int x,len;
    inline node(int a=0,int b=0) {
        x=a;
        len=b;
    }
    inline bool operator<(node a)const {
        return len>a.len;
    }
};

int n,m,k,t,tot;
int lim[25],dis[20005],a[25][25];
ll f[25][1<<20];
vector<node>g[20005];
priority_queue<node>q;

inline void djs(int s)
{
    for(int i=1; i<=n; i++) dis[i]=inf;
    dis[s]=0;
    q.push(node(s,0));
    while(!q.empty()) {
        int x=q.top().x;
        int len=q.top().len;
        q.pop();
        if(len!=dis[x]) continue;
        for(int i=g[x].size()-1; i>=0; i--) {
            int p=g[x][i].x;
            len=g[x][i].len;
            if(dis[p]<=dis[x]+len) continue;
            dis[p]=dis[x]+len;
            q.push(node(p,dis[p]));
        }
    }
    a[s][0]=dis[n];
}

int i;
int main()
{
    read(n),read(m),read(k);
    for(i=1; i<=m; i++) {
        int x,y,z;
        read(x),read(y),read(z);
        g[x].push_back(node(y,z));
        g[y].push_back(node(x,z));
    }
    read(t);
    for(i=1; i<=t; i++) {
        int x,y;
        read(x),read(y);
        lim[y]|=1<<(x-1);
    }

    k++;
    for(i=1; i<=k; i++) {
        djs(i);
        for(int j=1; j<=k; j++)
            a[i][j]=dis[j];
    }
    tot=(1<<k)-1;
    for(i=1,lim[i]|=1; i<=k; i++,lim[i]|=1)
        for(int j=0; j<=tot; j++)
            f[i][j]=inf;
    for(i=1; i<=k+1; i++) f[i][1<<(i-1)]=0;
    for(i=1; i<=tot; i++) {
        for(int j=1; j<=k; j++) {
            if((i|(1<<(j-1)))!=i) continue;
            if((i|lim[j])!=i) continue;
            for(int p=1; p<=k; p++) {
                if((i|(1<<(p-1)))==i) continue;
                if((i|lim[p])!=i) continue;
                f[p][i|(1<<(p-1))]=min(f[p][i|(1<<(p-1))],(ll)f[j][i]+a[j][p]);
            }
        }
    }

    ll ans=inf;
    for(int i=1; i<=k; i++)
        ans=min(ans,(ll)f[i][tot]+a[i][0]);
    write(ans);
    fwrite(pbuf,1,pp-pbuf,stdout);
}

Leave a Reply

Your email address will not be published. Required fields are marked *