四道比较水的题
T1：SPFA+状压
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
],dis[][],num,N,f[<<][],ans,vis[],mp[][];
void get_dis(int num){
queue<,sizeof(vis));
Q.push(num); dis[num][num]=INF; vis[num]=;
while (!Q.empty()){
int now=Q.front(); Q.pop();
; i<=n; i++){
){
dis[num][i]=max(dis[num][i],min(dis[num][now],mp[now][i]));
;
}
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &K);
; i<=K; i++) scanf("%d", &id[i]);
memset(dis,,sizeof(dis));
,u,v,w; i<=m; i++) scanf("%d%d%d", &u, &v, &w),mp[v][u]=mp[u][v]=w;
; i<=n; i++) get_dis(i);
N=(<<K);
; i<=K; i++) f[<<(i-)][i]=;
; s<N; s++){
num=;
; i<=K; i++) <<(i-))) num++;
; i<=K; i++) <<(i-))){
; j<=K; j++) <<(j-))))
<<(j-))][j]|=f[s][i];
}
; i<=K; i++) <<(i-))) && f[s][i]){
]);
ans=max(ans,t);
}
}
printf("%d\n", ans);
;
}
T2：裸RMQ
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
;
];
int main(){
scanf("%d%d", &n, &m);
; i<=n; i++) scanf(]);
; (<<j)<=n; j++)
; i+(<<(j-))<=n; i++)
f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
,a,b; i<=m; i++){
scanf("%d%d", &a, &b);
)/log();
printf(<<t)+][t]));
}
;
}
T3：曼哈顿距离转切比雪夫距离
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define INF 1000010
using namespace std;
int n,a,b,x,y,mxx,mxy,mnx,mny;
int main(){
scanf("%d", &n);
mxx=mxy=-INF; mnx=mny=INF;
; i<=n; i++){
scanf("%d%d", &a, &b);
x=b+a; y=b-a;
mnx=min(mnx,x); mxx=max(mxx,x);
mny=min(mny,y); mxy=max(mxy,y);
}
printf("%d\n", max(mxx-mnx,mxy-mny));
;
}
T4：set+最短路
#include<stdio.h>
#include<string.h>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
;
struct node{
int x,y,id;
friend bool operator<(node a, node b){
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
};
int n,t,x[maxn],y[maxn],dis[maxn];
queue<int> Q;
set<node> st;
node mk(int x, int y, int id){
node a; a.x=x; a.y=y; a.id=id; return a;
}
int main(){
scanf("%d%d", &n, &t);
; i<=n; i++){
scanf("%d%d", &x[i], &y[i]);
st.insert(mk(x[i],y[i],i));
}
dis[]=; x[]=y[]=;
Q.push();
while (!Q.empty()){
int now=Q.front(); Q.pop();
; i<=; i++) ; j<=; j++){
int X=x[now]+i, Y=y[now]+j;
));
if (next!=st.end()){
dis[next->id]=dis[now]+;
Q.push(next->id);
if (Y>=t){
printf("%d\n", dis[next->id]);
;
}
st.erase(next);
}
}
}
puts("-1");
;
}