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

## T1 repair Highway”

### \(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()
{
}

template<typename T>
{
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()
{
for(int i=1; i<=m; i++) {
int x,y,c1,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

### \(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()
{
}

template<typename T>
{
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()
{
for(int i=1; i<=m; i++) {
int x,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”

### \(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()
{
}
template<typename T>
{
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()
{
for(i=1; i<=m; i++) {
int x,y,z;
g[x].push_back(node(y,z));
g[y].push_back(node(x,z));
}
for(i=1; i<=t; i++) {
int x,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);
}``````