|
楼主 |
发表于 2018-12-12 16:31:27
|
显示全部楼层
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=102;
- const int INF=1<<30;
- struct edge
- {
- int fr,to,w,nxt;
- //int samee;
- bool deleted,inmst;
- bool operator < (const edge &a) const {
- return w<a.w;
- }
- };
- int pre[N],n,m,head[N],cnt,tmp=0;
- edge e[N*(N-1)+5];
- void add(int fr,int to,int w)
- {
- e[cnt].fr=fr;
- e[cnt].to=to;
- e[cnt].w=w;
- e[cnt].nxt=head[fr];
- e[cnt].deleted = false;
- e[cnt].inmst=false;
- head[fr]=cnt++;
-
- }
- int fin(int x)
- {
- if(x==pre[x])
- return x;
- return pre[x]=fin(pre[x]);
- }
- int Kruskal1()
- {
-
- for(int i=1;i<=n;++i)
- pre[i]=i;
- sort(e,e+2*m);
- int ans=0;
-
- for(int i=0;i<cnt;++i)
- {
- //if (e[i].deleted == true){continue;}
- int u=fin(e[i].fr);
- int v=fin(e[i].to);
-
- if(u!=v)
- {
-
- ans+=e[i].w;
- e[i].inmst=true;
- //tmp++;
- pre[u]=v;
- }
- }
- return ans;
- }
- int Kruskal2()
- {
-
- for(int i=1;i<=n;++i)
- pre[i]=i;
- sort(e,e+cnt);
- int ans=0;
-
- for(int i=0;i<cnt;++i)
- {
- if (e[i].deleted == true){/*cout << 1 << endl;*/continue;}
- int u=fin(e[i].fr);
- int v=fin(e[i].to);
- // cout << e[i].deleted << endl;
- if(u!=v)
- {
-
- ans+=e[i].w;
- //e[i].inmst=true;
-
- pre[u]=v;
- }
- }
- return ans;
- }
- int main()
- {
- int a,b,c;
- int T;
- cin >> T;
- while (T--)
- {
- cin >> n >> m;
- //while(scanf("%d",&n)&&n)
- //{
- cnt=0;
- //int m=n*(n-1)/2;
- memset(head,-1,sizeof(head));
- for (int i=0;i<m;i++)
- {
- scanf("%d%d%d",&a,&b,&c);
- add(a,b,c);
- add(b,a,c);
- /* int gg;
- // gg=e[cnt
- e[cnt-1].samee=cnt-2;
- e[cnt-2].samee=cnt-1;
- printf("%d %d\n",e[cnt-1].samee,e[cnt-2].samee);*/
- }
-
-
- printf("%d ",Kruskal1());
- //cout << cnt << endl;
- int smst = 999999999;
- for (int i=0;i<cnt;i++)
- {
- if (e[i].inmst==true)
- {
- e[i].deleted = true;
- e[i+1].deleted=true;
- //cout << smst << endl;
- smst=min(smst,Kruskal2());
- e[i].deleted= false;
- e[i+1].deleted = false;
- }
- }
- printf("%d\n",smst);
- }
- return 0;
- }
复制代码
这个代码可能有问题,但是思路是对的。 |
|