Day10

2018-08-21

字数统计: 1.2k字 | 阅读时长: 6min

网络会议（copy会议）

直接上代码。。。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int ne,to;
}edge[110000];
int head[51000],cnt;
void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}
int n,sz[51000],mn=0x7ffffff,ans1,ans2;
void dfs(int x,int fa)
{
    sz[x]=1;
    int blance=0;
    for(int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,x);
        sz[x]+=sz[v];
        blance=max(blance,sz[v]);
    }
    blance=max(blance,n-sz[x]);
    if(blance<mn||(blance==mn&&x<ans1))
    mn=blance,ans1=x;
}
int dis[51000];
void dfs1(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dis[v]=dis[x]+1;
        dfs1(v,x);
    }
}
int main()
{
//	freopen("meeting.in","r",stdin);
//	freopen("meeting.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v; 
        scanf("%d %d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    dfs1(ans1,0);
    for(int i=1;i<=n;i++)
    ans2+=dis[i];
    printf("%d %d",ans1,ans2);
    return 0;
}

有题目可得所求点为树的重心，然后得解。

虚拟路径（copy最小差值生成树）

数据范围缩小：对于 30%的数据， 1≤n≤m≤20。
对于 100%的数据， 1≤n≤m≤5000,0≤c≤50000。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0x7fffffff;
struct node
{
	int fr,to,w;
}edge[30000];
int cmp(node a,node b)
{
	return a.w<b.w;
}
int fa[51000];
int find(int x)
{
	return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void kr(int x)
{
	int i,tot=0,last;
	for(i=x;i<=m;i++)
	{
		int u=edge[i].fr,v=edge[i].to;
		int fu=find(u),fv=find(v);
		if(fu==fv) continue;
		fa[fu]=fv;
		tot++;
		last=i;
		if(tot==n-1) break;
	}
	if(tot==n-1) ans=min(edge[last].w-edge[x].w,ans);
	for(i=1;i<=n;i++) fa[i]=i;
}
int main()
{
	freopen("dvalue.in","r",stdin);
	freopen("dvalue.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&edge[i].fr,&edge[i].to,&edge[i].w);
	}
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++)
	kr(i);
	printf("%d",ans);
	return 0;
}

这好像是唯一一道我在考场上就切的题，然而freopen写错了！！！！！

这道题核心：按边权从小到大排序，枚举起点i,从i到m跑最小生成树，若能跑完，更新差值。

方块（并未找到相似题……）（好的BZOJ的4500）

【 问题描述】
方方方有着操控方块矩阵的能力， 它可以指定一个 n*m方块矩阵(初始时均为 0)中某一行或某一列方格的价值加 1 或减 1， fjzzq2002 觉得这样不行， 这样太无趣了。 
于是 fjzzq2002 给出了方方方 k 个限制， 每个限制为一个三元组(a,b,c)， 代表格子(a,b)在操作结束后的价值要等于 c， 然后询问方方方是否存在这样的操作序列满足他给出的限制。
方方方觉得 fjzzq2002 的要求太过分了， 于是向方老师求助。 方老师觉得这是一道好题， 于是交给了你。 如果存在输出” Yes” ， 否则输出” No” 。
【 输入格式】
第一行为一个正整数 T， 代表输入有 T 组数据。
对于每组数据第一行三个整数 n, m, k。
接下来 k 行， 每行三个整数 a, b, c。
【 输出格式】
对于每组数据， 输出 Yes 或者 No。
输入：            输出：

2               Yes
1 2 2           No
1 1 7
1 2 7
2 2 4
1 1 7
1 2 7
2 1 33
2 2 32


差分约束...完全不会做啊！qwq！，还好有正解。

#include<bits/stdc++.h>
using namespace std;
int T;
struct node{
	int ne,to,w;
}edge[100000];
int head[5000],cnt;		
int n,m,k;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w =w;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
int cn[5000],vis[5000],dis[5000];
int spfa()
{
	queue<int> q;
	for(int i=1;i<=n+m;i++)
	{
		q.push(i);
		dis[i]=0;
		vis[i]=1;
		cn[i]=1;
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
					cn[v]++;
					if(cn[v]>n+m) return -1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d",&T);
	for(int j=1;j<=T;j++)
	{
		memset(head,0,sizeof(head));
		cnt=0;
		scanf("%d %d %d",&n,&m,&k);
		for(int i=1;i<=k;i++)
		{
			int x,y,w;
			scanf("%d %d %d",&x,&y,&w);
			add(y+n,x,w);
			add(x,y+n,-w);
		}
		if(spfa()==-1) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

将a+b=c化为a-(-b)<=c和(-b)-a<=-c,连边跑spfa，若无环，就是唯一解或无限解.否则输出NO，其中-b和b+n都是列b的编号。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/536ffd33.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！