zhangas

Pay more attention

0%

7.28SDKDACM

Posted on

P3906 Geodetic集合

题目链接
无向图边长度为1 Q次询问求两点u，v之间最短距离经过的点集
N<=40 floyed处理多源最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
        else g[i][j]=0;
    }
}
floyed();
//枚举询问a和b之间的点i 满足g[a][i]+g[i][b]
while(q--){
    int a=read(),b=read();
    vector<int>v;
    v.push_back(a),v.push_back(b);
    for(int i=1;i<=n;i++){
        if(i!=a&&i!=b){
            if(g[a][i]+g[i][b]==g[a][b]){
                v.push_back(i);
            }
        }
    }
    sort(v.begin(),v.end());
    for(auto &i:v)cout<<i<<' ';
    puts("");

}

P2850 [USACO06DEC] Wormholes G

题目链接
m条路线(无向边) 从u到v花费时间p
w个虫洞(有向边) 从u到v可以回到时间p之前
判断是否可以回到出发点同时也是出发时刻以前的某一时刻
spfa判断是否存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int idx,e[2505],ne[2505],h[2505],w[2505];
int cnt[405];
int st[405];
int dist[405];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;//加入集合
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            //t->j
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return false;
}
void solve(){
    memset(h,-1,sizeof(h));
	memset(e,0,sizeof(e));
	memset(ne,0,sizeof(ne));
	memset(w,0,sizeof(w));
	memset(cnt,0,sizeof(cnt));
	memset(st,0,sizeof(st));
    idx=0;
    while(m--){
		int a=read(),b=read(),c=read();
		add(a,b,c),add(b,a,c);
	}
	while(p--){
		int a=read(),b=read(),c=read();
		add(a,b,-c);
	}
}

P8893 「UOI-R1」智能推荐

题目链接
从第0天开始 每一天你可以做以前推荐过的或者当天推荐的题
但有r个规则 在做第i道前要完成s道题目
求出做出第K道题需要的天数 如果不可以输出-1

从所有入度为0的点出发 跑一遍最短路dist[k]==0x3f3f3f3f时不能实现
注意N<=500但是有T组数据 T<=5 不可以Floyed求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<int>a[505];//存图
void spfa(){
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto &i:a[t]){
			ru[i]--;
			if(!ru[i]){
				dist[i]=min(dist[i],dist[t]+1);
				q.push(i);
			}
		}
    }
    if(dist[k]==0x3f3f3f3f)cout<<"-1";
    else cout<<dist[k];
}
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=p;i++){
    int t=read();
    dist[t]=0;//出发点处理
    q.push(t);
}
int r=read();
for(int i=1;i<=r;i++){
    int v=read(),s=read();
    while(s--){
        int t=read();
        //t->v有向边
        a[t].push_back(v);
        ru[v]++;
    }
}
spfa();

P4826 [USACO15FEB] Superbull S

题目链接
给N个数 以任意两个数的异或为边长建图 求其最大生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int f[2005];
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
struct Edge{
    int a,b,c;
}edges[4000005];//边为(N+1)*n/2条
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
int a[2005];
int n=read();
for(int i=1;i<=n;i++){
    f[i]=i;
}
int m=0;
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        edges[m++]={i,j,a[i]^a[j]};
    }
}
sort(edges,edges+m,cmp);
int ans=0;
for(int i=0;i<m;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(x!=y){
        f[x]=y;
        ans+=w;
        cnt++;
    }
    if(cnt==n-1)break;
}
cout<<ans;

P1744 采购特价商品

题目链接
给出N个点坐标和M对点之间有通路 且以两点之间的距离作为边权 求第S个点到第T个点的最短距离
N<=100 floyed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int x[105],y[105];
double g[105][105];
void floyed(){
    ...
}
int n=read();
for(int i=1;i<=n;i++){
    x[i]=read(),y[i]=read();
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
    }
}
int m=read();
while(m--){
    int a=read(),b=read();
    int xx=x[a]-x[b],yy=y[a]-y[b];
    dist[a][b]=min(dist[a][b],sqrt(xx*xx+yy*yy));
    dist[b][a]=min(dist[b][a],sqrt(xx*xx+yy*yy));
}
floyed();
int s=read(),t=read();
cout<<dist[s][t];

P2700 逐个击破

题目链接
N个城市由N-1条线路相连 其中K个是红点(不能在同一个连通块内)
给出N-1条可删去的线路和代价 求最小代价
最小代价==所有代价之和-尽可能多连接的线路之和
连通块维护 查询 vis[]数组标记是否产生冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
struct Edge{
    int a,b,c;
}edges[100005];
int n=read(),k=read();
for(int i=0;i<k;i++){
    int t=read();
    vis[t]=1;
}
int sum=0;
for(int i=1;i<=n;i++){
    f[i]=i;
}
for(int i=0;i<n-1;i++){
    int a=read(),b=read(),c=read();
    sum+=t;
    edges[i]={a,b,c};
}
sort(edges,edges+n-1,cmp);
int res=0;
for(int i=0;i<n-1;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(vis[x]==0||vis[y]==0){//两个点至少有一个不是敌人
        f[x]=y;
        res+=w;
        if(vis[x])vis[y]=1;
        if(vis[y])vis[x]=1;//同一连通块内不能连接两个敌人
    }
}
cout<<sum-res;