博客

2022.11.9~11

P1345 [USACO5.4]奶牛的电信Telecowmunication



P3931 SAC E#1 – 一道难题 Tree


最小割板子，写的时候只知道打最大流板子，没有理解最大流与最小割的联系，通过这题更好地理解了两者的关系

P2740 [USACO4.2]草地排水Drainage Ditches



P2936 [USACO09JAN]Total Flow S


纯最大流板子，看题的时候没注意到雨水只能沿一个方向移动，熟悉最大流板子

P2857 [USACO06FEB]Steady Cow Assignment G


分析题目，答案具有单调性，二分答案ans。check函数中我们只需枚举某一个区间（长度为ans），再对此时的区间建图，每只奶牛连向可以去的牛棚，建立超级源点和超级汇点，牛棚边权值即最大容量，最后跑最大流判断是否每头奶牛都有牛棚住即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e5+10;
const int N=2025;
const int inf=1e9;
struct edge
{
    int v,w,next;
}e[M];
int s,t,cnt,n,b,a[N][25],v[25];
int head[N],dep[N];
void ins(int u,int v,int w)
{
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
bool bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    dep[s]=1;
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if (!dep[v]&&e[i].w)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if (dep[t])
            return 1;
    return 0;
}
int dfs(int u,int dfrom)
{
    if (u==t)
        return dfrom;
    int dto=0;
    for (int i=head[u];i&&dfrom;i=e[i].next)
    {
        int v=e[i].v;
        if (dep[v]==dep[u]+1&&e[i].w)
        {
            int res=dfs(v,min(dfrom,e[i].w));
            dto+=res;
            dfrom-=res;
            e[i].w-=res;
            e[i^1].w+=res;
        }
	}
    if (!dto)
        dep[u]=-1;
    return dto;
}
bool dinic()
{
    int sum=0;
    while (bfs())
    {
        sum+=dfs(s,inf);
    }
    if (sum==n)
        return 1;
    return 0;
}
bool check(int x)
{
    for (int j=1;j+x-1<=b;j++)
    {
    	cnt=1;
    	memset(head,0,sizeof(head));
        for (int k=1;k<=n;k++)
        {
            ins(s,k,1);
            ins(k,s,0);
        }
        for (int k=1;k<=b;k++)
        {
            ins(k+n,t,v[k]);
            ins(t,k+n,0);
        }
        for (int i=1;i<=n;i++)
        {
        	for (int k=j;k<=j+x-1;k++)
            {
            	ins(i,a[i][k]+n,1);
				ins(a[i][k]+n,i,0);
			}
		}
        
        if (dinic())
        	return 1;
    }
    return 0;
}
void solve()
{
    cin>>n>>b;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=b;j++)
            cin>>a[i][j];
    for (int i=1;i<=b;i++)
        cin>>v[i];
    int l=0,r=b,ans;
    s=n+b+1,t=n+b+2;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid))
            r=mid-1,ans=mid;
        else
            l=mid+1;
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

George and Interesting Graph


首先考虑中心点，n较少，暴力枚举中心点，其它点都必须与中心点连两条边，于是维护每个点入度和出度，此时贡献为2*n-1-ru-chu，然后对于其它非中心点，只需让其再有一条边出和一条边进，也就是这些点只能匹配（指向）某一个点，于是建模为二分图最大匹配问题（最大为p），最后答案贡献为加边:n-1-p，减边：m-ru-chu-p；

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=505;
const int M=1e3+5;
struct edge1
{
	int v,next;
}e[M];
int head[N];
int n,m,ru[N],chu[N],cnt,dfn[N<<1],mch[N<<1];
void ins(int u,int v)
{
	cnt++;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
bool dfs(int u,int dtime,int mid)
{
	for (int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if (v==mid+n)
			continue;
		if (dfn[v]!=dtime)
		{
			dfn[v]=dtime;
			if ((!mch[v])||dfs(mch[v],dtime,mid))
			{
				mch[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int pan(int u)
{
	memset(mch,0,sizeof(mch));
	memset(dfn,0,sizeof(dfn));//忘记初始化了 
	int use=2*n-1-chu[u]-ru[u];
	int p=0;
	for (int i=1;i<=n;i++)
		if (i!=u)
			p+=dfs(i,i,u);
//	cout<<u<<" "<<p<<"\n";
	return use+(n-1-p)+(m-chu[u]-ru[u]-p);
}
void solve()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		ins(u,v+n);
		ru[v]++;
		chu[u]++;
		if (u==v)
			chu[u]--;
	}
	int ans=1e9;;
	for (int i=1;i<=n;i++)
	{
		ans=min(ans,pan(i));
	}
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();
	return 0;
}