点击这里进入题目
题意：有N个顶点M条边，每一条边都有相应的长度，你有长度为5和长度为6的线，你要用它来覆盖这些边，使花费最小。
思路：一个图上要求最小的花费，很明显要先处理最小生成树
AC程序
//库省略
using namespace std;
const int maxn=10005;
int n,m,k;
int fa[maxn];
int mst[maxn];
int num5,num6,cost5,cost6,i5=5,i6=6;
bool vis[maxn];
set<int> edge5,edge6;
int dp[maxn];
struct edge
{
int x,y,l,id;
} e[maxn];
bool cmp(edge a,edge b)
{
return a.l<b.l;
}
int findfa(int x)
{
if(fa[x]==x)
return x;
else
return fa[x]=findfa(fa[x]);
}
void MST()
{
k=0;
for(int i=0;i<m;i++)
{
int u=e[i].x,v=e[i].y;
int fu=findfa(u),fv=findfa(v);
if(fu!=fv)
{
fa[fu]=fv;
mst[k++]=i;
}
}
}
void solve1()
{
if(cost5>cost6)
{
swap(num5,num6);
swap(cost5,cost6);
swap(i5,i6);
}
}
int main()
{
freopen("domestic.in","r",stdin);
freopen("domestic.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=0;i<m;i++)
{
cin>>e[i].x>>e[i].y>>e[i].l;
e[i].id=i+1;
}
sort(e,e+m,cmp);
MST();
cin>>cost5>>num5>>cost6>>num6;
solve1();
if(k!=n-1)
{
cout<<"Impossible"<<endl;
return 0;
}
vis[0]=1;
for(int i=0;i<k;i++)
{
int now=mst[i];
int len=e[now].l;
edge6.insert(now);
for(int j=num5;j>=len;j--)
{
if(!vis[j] && vis[j-len])
{
vis[j]=1;
dp[j]=mst[i];
}
}
}
int t=num5;
while(!vis[t])
t--;
while(t>0)
{
edge5.insert(dp[t]);
edge6.erase(dp[t]);
t-=e[dp[t]].l;
}
int ans5=0,ans6=0;
for(set<int>::iterator it=edge5.begin();it!=edge5.end();it++)
ans5+=e[*it].l;
for(set<int>::iterator it=edge6.begin();it!=edge6.end();it++)
ans6+=e[*it].l;
if(ans5<=num5 && ans6<=num6)
{
ll ans=(ans5*cost5)+(ans6*cost6);
cout<<ans<<endl;
for(set<int>::iterator it=edge5.begin();it!=edge5.end();it++)
cout<<e[*it].id<<" "<<i5<<endl;
for(set<int>::iterator it=edge6.begin();it!=edge6.end();it++)
cout<<e[*it].id<<" "<<i6<<endl;
}
else
{
cout<<"Impossible"<<endl;
return 0;
}
return 0;
}