高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=1532

题意

n个人，m场比赛，求赢得最多的人最少赢多少场。

题解

二分答案X；

S向每场比赛连边，容量为1；

每场比赛向参赛的两个人连边容量oo；

每个人向T连边，容量为X。

如果答案合法，最大流为m。

sap卡了，不知道为什么在这种二分图上dinic会快

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
const int N=20011,M=5*N;
int u[M],v[M],w[M],next[M],head[N],cur[N],k;
int n,m,a[10001],b[10001];
int s,t,pre[N],low[N],d[N],vd[N];
queue<int> q;
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
 
bool bfs()
{
    int now;bool flag=false;
    memset(d,-1,sizeof(d));
    q.push(t);d[t]=0;
    while(!q.empty())
    {
        now=q.front();q.pop();
        for(int i=head[now];i;i=next[i])
            if(d[v[i]]==-1 && w[i^1])
            {
                d[v[i]]=d[now]+1;
                q.push(v[i]);
                if(v[i]==s) flag=true;
            }
    }
    return flag;
}
int dfs(int now,int low)
{
    if(now==t)  return low;
    int ret=low,tmp;
    for(int i=head[now];i;i=next[i])
    {
        if(d[v[i]]!=d[now]-1 || !w[i])  continue;
        tmp=dfs(v[i],min(low,w[i]));
        low-=tmp;
        w[i]-=tmp;w[i^1]+=tmp;
        if(low==0)  break;
    }
    if(low==ret)d[now]=-1;
    return ret-low;
}
int solve()
{
    int ans=0,flow;
    while(bfs())
        while(flow=dfs(s,INT_MAX))
            ans+=flow;
    return ans;
}
void build(int x)
{
    memset(head,0,sizeof(head));k=1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,1);
        add(i,m+a[i],1);add(i,m+b[i],1);
    }
    for(int i=1;i<=n;i++)
        add(m+i,t,x);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",a+i,b+i);
    s=n+m+1;t=s+1;
    int l=1,r=m,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        build(mid);
        if(solve()==m)  r=mid-1;
        else    l=mid+1;
    }
    printf("%d\n",l);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1131

题意

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

题解

感觉会爆栈，写的BFS，代码太渣了，

cost[i]记以这点为根的深度之和，sum[i]为i的子树大小。

#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000001,M=N*2;
int n,u[M],v[M],next[M],head[N],k;
int q[N],fa[N];
long long sum[N],cost[N];
 
void add(int x,int y)
{
    u[++k]=x;v[k]=y;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;next[k]=head[y];head[y]=k;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);
    }
    int l=0,r=1;q[1]=1;fa[1]=0;
    while(l<r)
    {
        int now=q[++l];
        for(int i=head[now];i;i=next[i])
            if(fa[now]!=v[i])
            {
                fa[v[i]]=now;
                q[++r]=v[i];
            }
    }
    for(int i=r;i>0;i--)
    {
        sum[q[i]]+=1;
        sum[fa[q[i]]]+=sum[q[i]];
        cost[fa[q[i]]]+=cost[q[i]]+sum[q[i]];
    }
    long long MAX=cost[1];int ans=1;
    for(int i=2;i<=r;i++)
    {
        cost[q[i]]=cost[fa[q[i]]]-(sum[q[i]]<<1)+n;
        if((cost[q[i]]>MAX)||(cost[q[i]]==MAX && q[i]<ans))
            MAX=cost[q[i]],ans=q[i];
    }
    printf("%d\n",ans);
}