题目:https://odzkskevi.qnssl.com/95fc8c37ba05359d81df6779e817c236?v=1501937229
因为q很小,所以直接枚举所有的方案就行。
首先求不用方案时的最小生成树,然后每次枚举方案时只需考虑初次最小生成树中的边就可以,如果每次都用所有边会tle。
感觉自己写的又长又蠢。。。
二进制枚举
for(int i=0;i<(1<<q);i++)
{
if(i&(1<<j))
{}
}
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int maxn=1000004/2;
int n,q,cnt;
struct Edge
{
int u,v,len;
}edge[maxn];
struct Way
{
int num,cost,citys[1005];
}ways[10];
int r[maxn],p[1005];
pii City[1005];
vector<Edge>minrode;
int dis(pii a,pii b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
int cmp(int a,int b)
{
return edge[a].len<edge[b].len;
}
void init()
{
for(int i=0;i<=n;i++)
p[i]=i;
}
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int kruskal()
{
int ans=0;
for(int i=0;i<cnt;i++) r[i]=i;
sort(r,r+cnt,cmp);
minrode.clear();
for(int i=0;i<cnt;i++)
{
int e=r[i],x=find(edge[e].u),y=find(edge[e].v);
if(x!=y)
{
ans+=edge[e].len;
p[x]=y;
minrode.push_back(edge[e]);
}
}
return ans;
}
int __kruskal()
{
int ans=0;
//for(int i=0;i<cnt;i++) r[i]=i;
//sort(r,r+cnt,cmp);
for(int i=0;i<minrode.size();i++)
{
int x=find(minrode[i].u),y=find(minrode[i].v);
if(x!=y)
{
ans+=minrode[i].len;
p[x]=y;
}
}
return ans;
}
void solve()
{
init();
int ans=kruskal();
for(int i=0;i<(1<<q);i++)
{
init();
int tol=0;
for(int j=0;j<q;j++)
{
if(i&(1<<j))
{
tol+=ways[j].cost;
for(int k=1;k<ways[j].num;k++)
{
int x=find(ways[j].citys[0]),y=find(ways[j].citys[k]);
if(x!=y)
{
p[y]=x;
}
}
}
}
ans=min(ans,tol+__kruskal());
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>q;
for(int i=0;i<q;i++)
{
cin>>ways[i].num>>ways[i].cost;
for(int j=0;j<ways[i].num;j++)
cin>>ways[i].citys[j];
}
int x,y;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
City[i]=make_pair(x,y);
}
cnt=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].len=dis(City[i],City[j]);
}
solve();
if(t) cout<<endl;
}
return 0;
}