[Luogu3264]
原題解
多個頻道,每個頻道的關鍵點要求相互聯通
詳見代碼,非常巧妙
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x;
}const int MAXN=1005;
const int MAXM=6005;
const int MAXL=1<<10;struct Edge{int v,w,c,next;
}e[MAXM];
int first[MAXN],Ecnt=1;
inline void Add_edge(int u,int v,int w=0,int c=0){e[++Ecnt]=(Edge){v,w,c,first[u]};first[u]=Ecnt;
}struct Point{int col,id;inline friend bool operator < (Point a,Point b){return a.col<b.col;}
}a[12];int f[MAXN][MAXL],g[MAXL];
bool inq[MAXN];
int n,m,K,Cnt;
queue <int> q;inline void SPFA(int sta){while(!q.empty()){int u=q.front();q.pop();inq[u]=false;for(int i=first[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if(f[u][sta]+w<f[v][sta]){f[v][sta]=f[u][sta]+w;if(!inq[v]) inq[v]=true,q.push(v);}}}
}inline int solve(int cnt){//一共只要考慮cnt個點for(int i=1;i<(1<<cnt);i++){//這一維為基礎:狀態for(int j=1;j<=n;j++){for(int k=(i-1)&i;k;k=(k-1)&i)f[j][i]=min(f[j][i],f[j][k]+f[j][i^k]);//再枚舉j:以j為根連接狀態了j的點if(f[j][i]<f[0][0])inq[j]=1,q.push(j);}SPFA(i);//我理解為暴力散開}int res=INF;for(int i=1;i<=n;i++) res=min(res,f[i][(1<<cnt)-1]);return res;
}int main(){n=read(),m=read(),K=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();Add_edge(x,y,w);Add_edge(y,x,w);}for(int i=1;i<=K;i++)a[i].col=read(),a[i].id=read();sort(a+1,a+K+1);for(int i=1;i<=K;i++){if(a[i].col!=a[i-1].col) Cnt++;a[i].col=Cnt;//離散化}Cnt=1<<Cnt;memset(g,0x3f,sizeof g);for(int i=1;i<Cnt;i++){memset(f,0x3f,sizeof f);int tmp=0;for(int j=1;j<=K;j++){if((1<<(a[j].col-1))&i)f[a[j].id][1<<tmp++]=0;//i這些頻道共有tmp個點}g[i]=solve(tmp);//i這些頻道 <- 考慮這tmp個點的答案}for(int i=1;i<Cnt;i++){for(int j=(i-1)&i;j;j=(j-1)&i)g[i]=min(g[i],g[j]+g[i^j]);//再更新一次}printf("%d\n",g[Cnt-1]);
}
)
周報)
