[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]); }

轉載于:https://www.cnblogs.com/lizehon/p/10584549.html

總結

以上是生活随笔為你收集整理的[JLOI2015]管道连接（斯坦纳树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。