http://acm.timus.ru/problem.aspx?space=1&num=1128
思維才是最重要的 有些題目用不到很復(fù)雜的算法 甚至不用算法 但就是讓人很難想到
個(gè)人認(rèn)為這才是一個(gè)人能力的關(guān)鍵 還需要多加練習(xí)呀
此題：
首先 此題肯定有解 也就是說“NO SOLUTION”是騙人的
1.我們先把所以人放在一個(gè)組里
2.遍歷一遍 對于某個(gè)人如果同組中有兩個(gè)或兩個(gè)以上的敵人 則將此人放到另一組
3.如果 2 中沒有更新則結(jié)束 否則重復(fù) 步驟 2
時(shí)間復(fù)雜度 接近 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;
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
