Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数据好水啊数据好水啊 这个代码都能过。。。。 ///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unordered_set> #include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<queue> #include<bitset> #include<set> #include<stack> #include<map> #include<list> #include<new> #include<vector> #define MT(a,b) memset(a,b,sizeof(a)); using namespace std; typedef long long ll; typedef unsigned long long ull; const double pai=acos(-1.0); const double E=2.718281828459; const ll mod=998424353; const int INF=0x3f3f3f3f; int n,m; int st[205],en[205]; int p[205]; int s[40005],e[40005]; int sign; struct node { int s; int e; int c; bool friend operator<(node a,node b) { return a.c<b.c; } }edge[10005]; int find(int x) { return p[x]==x?x:p[x]=find(p[x]); } void init() { for(int i=1;i<=n;i++) p[i]=i; } int judge() { for(int i=1;i<=sign;i++) { int x=find(s[i]); int y=find(e[i]); if(x!=y) return 0; } return 1; } int main() { while(scanf("%d",&n)!=EOF,n) { int a=0,b=0; for(int i=1; i<=n; i++) { scanf("%d",&st[i]); a+=st[i]; } for(int i=1; i<=n; i++) { scanf("%d",&en[i]); b+=en[i]; } if(a>b) { printf("No Solution\n"); continue; } sign=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(st[i]-en[i]>0&&st[j]-en[j]<0) { s[++sign]=i; e[sign]=j; } } } scanf("%d",&m); for(int i=1; i<=m; i++) scanf("%d %d %d",&edge[i].s,&edge[i].e,&edge[i].c); sort(edge+1,edge+1+m); int flag=1; for(int i=1;i<=m;i++) { init(); for(int j=1;j<=i;j++) { int x=find(edge[j].s); int y=find(edge[j].e); if(x!=y) p[x]=y; } if(judge()) { flag=0; printf("%d\n",edge[i].c); break; } } if(flag) printf("No Solution\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator