题目链接:http://codeforces.com/problemset/problem/781/C
因为有${K}$个机器人,每个又可以走${\left \lceil \frac{2n}{k} \right \rceil}$步,所以这些机器人一共可以走的总步数就至少为${2n}$,然后再发现直接$DFS$整张图,记录经过的路径这样是不超过$2n$个点的,所以划分一下这个序列就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001000 10 #define llg int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,k,dl[maxn],tail,ans[maxn]; 13 vector<llg>a[maxn]; 14 bool bj[maxn]; 15 void init() 16 { 17 llg x,y; 18 cin>>n>>m>>k; 19 for (llg i=1;i<=m;i++) 20 { 21 scanf("%d%d",&x,&y); 22 a[x].push_back(y),a[y].push_back(x); 23 } 24 } 25 26 void dfs(llg x) 27 { 28 bj[x]=1; 29 llg w=a[x].size(),v; 30 dl[++tail]=x; 31 for (llg i=0;i<w;i++) 32 { 33 v=a[x][i]; 34 if (!bj[v]) 35 { 36 dfs(v); 37 dl[++tail]=x; 38 } 39 } 40 } 41 42 int main() 43 { 44 yyj("E"); 45 init(); 46 dfs(1); 47 llg l=1; 48 llg up=(2*n)/k,cs; 49 if ((n*2)%k) up++; 50 while (1) 51 { 52 if (l>tail) break; 53 k--; 54 cs=0; 55 while (l<=tail) 56 { 57 cs++; 58 if (cs>up) {cs--; break;} 59 ans[cs]=dl[l]; l++; 60 } 61 printf("%d ",cs); 62 for (llg i=1;i<=cs;i++) printf("%d ",ans[i]); 63 printf("\n"); 64 } 65 while (k--) 66 { 67 puts("1 1"); 68 } 69 return 0; 70 }