第一题
用堆维护。
#include <cstdio>
#include <algorithm>
#include <queue>
int n,i,f[400000],g[2][200000],j=0,k[400000];
int l,r;
bool cho;
struct pn{
int l,r,n;
};
bool operator<(pn a,pn b){
return a.n>b.n;
}
std::priority_queue<pn> q;
pn as,as1,as2;
int main(){
freopen("minval.in","r",stdin);
freopen("minval.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&g[0][i]);
for(i=0;i<n;++i) scanf("%d",&g[1][i]);
std::sort(g[0],g[0]+n);
std::sort(g[1],g[1]+n);
as.l=0;
as.r=0;
as.n=g[0][0]+g[1][0];
q.push(as);
for(i=0;i<n;++i){
as=q.top();
q.pop();
as1.l=as.l+1;
as1.r=as.r;
as1.n=g[0][as1.l]+g[1][as1.r];
as2.l=as.l;
as2.r=as.r+1;
as2.n=g[0][as2.l]+g[1][as2.r];
printf("%d ",as.n);
q.push(as1);
q.push(as2);
}
return 0;
}
第二题
连通性判定+二分图
#include <cstdio>
#include <cstring>
int f[200000],d,i,j,m,n,s,t,tt,a,b,pl,h[200000];
int q[200000],qh,qt;
bool f2;
struct edge{
int t,n;
} edges[2000000];
inline void addedge(int f,int t){
edges[++pl].n=h[f];
edges[ pl ].t= t ;
h[f]=pl;
}
int main(){
freopen("catch.in","r",stdin);
freopen("catch.out","w",stdout);
scanf("%d",&tt);
while(tt--){
++j;
memset(f,0,sizeof f);
memset(h,0,sizeof h);
pl=0;
qh=qt=0;
scanf("%d%d%d",&n,&m,&s);
for(i=0;i<m;++i){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
q[qt++]=s;
f2=false;
f[s]=1;
--n;
while(qh!=qt){
i=q[qh++];
for(d=h[i];d;d=edges[d].n){
t=edges[d].t;
if(!f[t]){
f[t]=3-f[i];
q[qt++]=t;
--n;
}else{
if(f[i]==f[t]) f2=true;//not bicolorable
}
}
}
if(!f2){
printf("Case %d: NO\n",j);
}else{
if(n) printf("Case %d: NO\n",j); else printf("Case %d: YES\n",j);
}
}
return 0;
}
第三題：二分答案加判定
#include <cstdio>
#include <cstring>
struct edge{
int t,n,w;
} e[300000];
int h[20000],pl;
inline void addedge(int f,int t,int w){
e[++pl].t=t;
e[pl].n=h[f];
e[pl].w=w;
h[f]=pl;
}
int n,m,u,v,s,i,j,k;
int left,right,mid,ans;
int cost[20000];
int q[100000],qh,qt;
bool iq[20000];
int f[20000];
int ka,kb,ww;
int v0,v1,e0;
void spfa(int mma){
memset(f,-1,sizeof f);
memset(iq,0,sizeof iq);
qh=qt=0;
q[qt++]=u;
f[u]=0;
while(qh!=qt){
v0=q[qh++];
iq[v0]=false;
for(e0=h[v0];e0;e0=e[e0].n){
v1=e[e0].t;
if(cost[v1]>mma) continue;
if(f[v1]==-1 || f[v1] > f[v0] + e[e0].w){
f[v1] = f[v0] + e[e0].w;
if(!iq[v1]){
iq[v1]=true;
q[qt++]=v1;
}
}
}
}
}
int main(){
freopen("cost.in","r",stdin);
freopen("cost.out","w",stdout);
scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);
left=0x7fffffff;
for(i=1;i<=n;++i){
scanf("%d",cost+i);
if(cost[i]<left) left=cost[i];
if(cost[i]>right) right=cost[i];
}
for(i=1;i<=m;++i){
scanf("%d%d%d",&ka,&kb,&ww);
addedge(ka,kb,ww);
addedge(kb,ka,ww);
}
spfa(right);
if(f[v]==-1 || f[v] > s){
printf("-1\n");
return 0;
}
while(left<=right){
mid=(left+right)/2;
spfa(mid);
if( f[v] == -1 || f[v] > s ){
left=mid+1;
}else{
right=mid-1;
ans=mid;
}
}
printf("%d\n",ans);
return 0;
}
更新：修復了exceed 32bit int的bug
#include <cstdio>
#include <cstring>
struct edge{
int t,n,w;
} e[300000];
long long h[20000],pl;
inline void addedge(int f,int t,int w){
e[++pl].t=t;
e[pl].n=h[f];
e[pl].w=w;
h[f]=pl;
}
long long n,m,u,v,s,i,j,k;
long long left,right,mid,ans;
long long cost[20000];
long long q[100000],qh,qt;
bool iq[20000];
long long f[20000];
long long ka,kb,ww;
long long v0,v1,e0;
void spfa(int mma){
memset(f,-1,sizeof f);
memset(iq,0,sizeof iq);
qh=qt=0;
q[qt++]=u;
f[u]=0;
while(qh!=qt){
v0=q[qh++];
iq[v0]=false;
for(e0=h[v0];e0;e0=e[e0].n){
v1=e[e0].t;
if(cost[v1]>mma) continue;
if(f[v1]==-1 || f[v1] > f[v0] + e[e0].w){
f[v1] = f[v0] + e[e0].w;
if(!iq[v1]){
iq[v1]=true;
q[qt++]=v1;
}
}
}
}
}
int main(){
freopen("cost.in","r",stdin);
freopen("cost.out","w",stdout);
scanf("%lld%lld%lld%lld%lld",&n,&m,&u,&v,&s);
left=0x7fffffff;
for(i=1;i<=n;++i){
scanf("%lld",cost+i);
if(cost[i]<left) left=cost[i];
if(cost[i]>right) right=cost[i];
}
for(i=1;i<=m;++i){
scanf("%lld%lld%lld",&ka,&kb,&ww);
addedge(ka,kb,ww);
addedge(kb,ka,ww);
}
spfa(right);
if(f[v]==-1 || f[v] > s){
printf("-1\n");
return 0;
}
while(left<=right){
mid=(left+right)/2;
spfa(mid);
if( f[v] == -1 || f[v] > s ){
left=mid+1;
}else{
right=mid-1;
ans=mid;
}
}
printf("%lld\n",ans);
return 0;
}