「BZOJ3624」[Apio2008] 免费道路
Description
Input
Output
Sample Input
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
Sample Output
3 2 0
4 3 0
5 3 1
1 2 1
4 3 0
5 3 1
1 2 1
题解
优先加1做生成树，得出必须添加的0的边
反过来，将0的边加至K条，再放1的边
|
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,top; int fa[20005]; int u[100005],v[100005],c[100005]; int au[20005],av[20005],ac[20005]; bool mark[100005]; int num[2]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void solve(bool typ,int mx) { for(int i=1;i<=m;i++) if(c[i]==typ&&num[typ]<mx) { int p=find(u[i]),q=find(v[i]); if(p!=q) { fa[p]=q; au[++top]=u[i],av[top]=v[i],ac[top]=c[i]; mark[i]=1;num[typ]++; } } } int main() { n=read();m=read();K=read(); for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),c[i]=read(); for(int i=1;i<=n;i++)fa[i]=i; num[0]=num[1]=0; solve(1,inf);solve(0,inf); if(num[1]+num[0]!=n-1||num[0]>K) { puts("no solution"); return 0; } top=0;num[0]=num[1]=0; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) if(c[i]==0&&mark[i]) { int p=find(u[i]),q=find(v[i]); if(p!=q) { num[0]++;fa[p]=q; au[++top]=u[i];av[top]=v[i];ac[top]=c[i]; } } solve(0,K);solve(1,inf); if(num[0]<K) { puts("no solution"); return 0; } for(int i=1;i<=top;i++) printf("%d %d %d\n",au[i],av[i],ac[i]); return 0; } |
Subscribe
计数器 9850892
OI 课件=>
OI 课件=>