zkx06111's Blog

//使用prim算法即可
#include <iostream>
#include <climits>
using namespace std;

int n,a[101][101],f[101],pre[101],s[101],t[101];
bool b[101];
int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j) {
			cin>>a[i][j];
			a[j][i]=a[i][j];
		}
	for (int i=1;i<=n;++i) f[i]=INT_MAX/3;
	f[1]=0; int cnt=n,ans=0,m=0;
	while (cnt--) {
		int p,v=INT_MAX/3;
		for (int i=1;i<=n;++i)
			if (f[i]<v && !b[i]) {
				p=i;
				v=f[i];
			}
		ans+=v; f[p]=0; b[p]=1;
		if (v!=0 && p!=1) { //如果是非0边，则记录下来
			++m;
			s[m]=pre[p];
			t[m]=p;
		}
		for (int i=1;i<=n;++i)
			if (f[p]+a[p][i]<f[i]) {
				f[i]=f[p]+a[p][i];
				pre[i]=p; //更新pre[i]
			}
	}
	cout<<m<<endl;
	for (int i=1;i<=m;++i)
		if (s[i]<t[i]) cout<<s[i]<<' '<<t[i]<<endl;
		else cout<<t[i]<<' '<<s[i]<<endl;
	cout<<ans;
	return 0;
}

//树状数组首杀！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define lowbit(x) ((x)&(-x))
#define MAXN 200005
 
using namespace std;
 
int tree[MAXN],top,n; //tree为树状数组；top为离散化后y的最大值
set<int> out; //out为输出的集合
struct Point {
    int x,y,rk; //x,y为坐标；rk代表按y离散化后的序号；
    int xn,yn; //xn,yn为该点所在横、竖线上点的个数；
    int ans, //ans为以该点来划分，Stan取得个数；
        mn; //mn为画过该点的竖线Stan取得个数的最小值；
}p[MAXN];
 
void add(int x,int v) {
    while (x<MAXN) {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
 
int get(int x) {
    int res=0;
    while (x) {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
 
int get(int x,int y) {
    return get(y)-get(x-1);
}
 
bool cmpy(Point a,Point b) {
    return a.y<b.y;
}
 
bool cmp1(Point a,Point b) {
    if (a.x==b.x) return a.y>b.y;
    return a.x<b.x;
}
 
bool cmp2(Point a,Point b) {
    if (a.x==b.x) return a.y<b.y;
    return a.x>b.x;
}
 
int main() {
    memset(tree,0,sizeof(tree));
    scanf("%d",&n);
    for (int i=0;i<n;++i) {
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].ans=p[i].xn=p[i].yn=0;
    }
    //读入
    sort(p,p+n,cmpy);
    top=1;
    for (int i=0;i<n;++i) {
        if (i && p[i].y!=p[i-1].y) ++top;
        p[i].rk=top; add(p[i].rk,1);
    }
    //离散化
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].y==p[j].y && j<n;++j) ++t;
        for (j=i;p[i].y==p[j].y && j<n;++j) p[i].yn=t;
        i=j-1;
    }
    //计算yn
    sort(p,p+n,cmp1);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(p[i].rk+1,top);
    }
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].x==p[j].x && j<n;++j) ++t;
        for (j=i;p[i].x==p[j].x && j<n;++j) p[i].xn=t;
        i=j-1;
    }
    //计算每个点右上方点的个数并同时计算yn
    memset(tree,0,sizeof(tree));
    for (int i=0;i<n;++i) add(p[i].rk,1); //把数组恢复原状
    sort(p,p+n,cmp2);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(1,p[i].rk-1);
    }
    //计算每个点左下方点的个数
    for (int i=0;i<n;++i) {
        int j,Min=99999999;
        for (j=i;p[i].x==p[j].x && j<n;++j) Min=min(p[j].ans,Min);
        for (j=i;p[i].x==p[j].x && j<n;++j) p[j].mn=Min;
        i=j-1;
    }
    //计算每条竖线Stan拿到的最小值
    int Max=0; out.clear();
    for (int i=0;i<n;++i) {
        if (p[i].mn!=p[i].ans) continue;
        if (p[i].ans>Max) {
            Max=p[i].ans;
            out.clear();
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1); //Ollie拿到的饼数
        }
        else if (p[i].ans==Max)
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1);
    }
    printf("Stan: %d; Ollie:",Max);
    for (set<int>::iterator it=out.begin(); it!=out.end();++it)
        printf(" %d",*it);
    printf(";\n");
    return 0;
}

//做法略暴力
#include <iostream>
using namespace std;

int n,a[101][101],l[101],r[101];

void edit(int x) //编辑结点x
{
    int last=0; //上一个x的子结点
    for (int i=1;i<=n;++i)
        if (a[x][i]) {
            if (last) { //若不是第一个结点
                a[x][i]=0;
                a[last][i]=1;
                r[last]=i;
            } //连接上一个结点与该结点，该结点作为上一个结点的右儿子
            else l[x]=i; //第一个结点作为父结点的左儿子
            last=i;
            edit(i); //递归的编辑结点i
        }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) {
        int t,x; cin>>t;
        for (int j=0;j<t;++j) {
            cin>>x;
            if (x) a[i][x]=1;
        }
    }
    edit(1);
    cout<<n<<endl;
    for (int i=1;i<=n;++i)
        cout<<l[i]<<' '<<r[i]<<endl;
    return 0;
}