【 Codeforces Round #518 (Div. 2) [Thanks, Mail.Ru!] C. Colored Rooks】 构造

C. Colored Rooks

题意

$这个题的题意有一些复杂，给你一个1e9?1e9的棋盘$
$给你n种棋子，m个关系$
$所有有关系的棋子必须在同一行同一列出现$
$所有不具有关系的棋子不能在同一行同一列出现$
$构造这个棋盘，每种棋子可以多次使用，总棋子数不能超过5000$
$1<=n<=1000<=m<=min(1000,n?(n?1)/2)$

做法
$由于每种棋子可以用多次，我们就每次就每次用两个棋子构造一种关系$
$如何构造比较好实现呢$
$每种棋子都放在一行，对每种关系，都在当前行新加棋子$
$在关系对应的棋子那一行也加上棋子，$
$为了不让这个关系对其他关系有影响，每次放棋子都让横坐标右移1$

注意每个棋子都要先于自己建立关系再右移
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 105;
int con[maxn][maxn];
vector<pii> ans[maxn];
int cnt[200];
int main()
{
    int n,m,x,y;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) con[i][i]=1;for(int i=1;i<=m;i++){
    scanf("%d%d",&x,&y);con[x][y]=1;con[y][x]=1;}int cnt=0;for(int i=1;i<=n;i++){
    ans[i].push_back(pii(++cnt,i));for(int j=i+1;j<=n;j++){
    if(con[i][j]){
    ans[i].push_back(pii(++cnt,i));ans[j].push_back(pii(cnt,j));}}}for(int i=1;i<=n;i++){
    printf("%d\n",ans[i].size());for(int j=0;j<ans[i].size();j++){
    printf("%d %d\n",ans[i][j].first,ans[i][j].second);}}return 0;
}