http://acm.timus.ru/problem.aspx?space=1&num=1128
思維才是最重要的 有些題目用不到很復雜的算法 甚至不用算法 但就是讓人很難想到
個人認為這才是一個人能力的關鍵 還需要多加練習呀
此題:
首先 此題肯定有解 也就是說“NO SOLUTION”是騙人的
1.我們先把所以人放在一個組里
2.遍歷一遍 對于某個人如果同組中有兩個或兩個以上的敵人 則將此人放到另一組
3.如果 2 中沒有更新則結束 否則重復 步驟 2
時間復雜度 接近 o(n^2)
可以接受
代碼:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<queue> #include<stack> #include<map> #include<string> #include<iomanip> using namespace std; #define LL long long const int INF=0x3f3f3f3f; const int N=10005; int head[N],I; struct node { int j,next; }side[N*50]; vector<int>group1; vector<int>group2; int in[N]; queue<int>qt; struct node1 { int out; int I; }mem[N]; void add(int i,int j) { side[I].j=j; side[I].next=head[i]; head[i]=I++; } bool cmp(node1 x,node1 y) { return x.out<y.out; } bool F(int k,int n) { bool log=false; for(int i=1;i<=n;++i) { if(in[i]==k) { int k=0; for(int t=head[i];t!=-1;t=side[t].next) { int l=side[t].j; if(in[l]==in[i]) ++k; } if(k>=2) {in[i]=-in[i];log=true;} } } return log; } int main() { //freopen("data.in","r",stdin); int n; while(cin>>n) { memset(head,-1,sizeof(head)); I=0; for(int i=1;i<=n;++i) { int m; cin>>m; while(m--) { int k; cin>>k; add(i,k); } } for(int i=1;i<=n;++i) in[i]=1; int k=1; while(F(k,n)) k=-k; group1.clear(); group2.clear(); for(int i=1;i<=n;++i) { if(in[i]==1) group1.push_back(i); else group2.push_back(i); } cout<<min(group1.size(),group2.size())<<endl; if(group1.size()<group2.size()||(group1.size()==group2.size()&&group1[0]==1)) for(unsigned int i=0;i<group1.size();++i) { if(i) cout<<" "; cout<<group1[i]; } else for(unsigned int i=0;i<group2.size();++i) { if(i) cout<<" "; cout<<group2[i]; } } return 0; }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
