bzoj泛做 - HZH's Blog - 独自舔舐伤口的老虎

bzoj泛做

nbdhhzh posted @ 2015年6月14日 21:09 in 屯题 , 898 阅读

每天bzoj水题切切啊!不会去切些有意义的题么?bzoj上面的题平均难度最低了!——某犇

(找个理由坑了


4155: [Ipsc2015]Humble Captains

合并了两道SB题。第一问网络流第二问DP即可。

#include<cstdio>
#include<bitset>
#include<cstring>
#include<algorithm>
#define INF 1e9
#define N 300
#define M 40010
using namespace std;
bitset<21000>f;
int Q,n,m,S,T,l,v[M],ne[M],fl[M],head[N],hash[N];
int cs[N],flow,now,i,kt[N],w[N],pre[N],ans,m1,gs[N],x,y;
void add(int x,int y,int f1,int f2)
{
	v[++l]=y;ne[l]=head[x];head[x]=l;fl[l]=f1;
	v[++l]=x;ne[l]=head[y];head[y]=l;fl[l]=f2;
}
void sap()
{
	memset(hash,0,sizeof(hash));
	memset(cs,0,sizeof(cs));cs[0]=T+1;
	hash[0]=T;flow=INF;now=S;
	for(i=1;i<=T;i++)kt[i]=head[i];
	for(;cs[S]<=T;)
	{
		w[now]=flow;
		for(i=kt[now];i;i=ne[i])
			if(cs[now]==cs[v[i]]+1&&fl[i])
			{
				flow=min(flow,fl[i]);
				kt[now]=i;
				pre[v[i]]=i;now=v[i];
				if(now==T)
				{
					ans+=flow;
					for(;now!=S;now=v[pre[now]^1])
						fl[pre[now]]-=flow,
						fl[pre[now]^1]+=flow;
					flow=INF;
				}
				break;
			}
		if(i)continue;m1=0;
		for(i=head[now];i;i=ne[i])
			if(cs[v[i]]<cs[v[m1]]&&fl[i])m1=i;
		if(!(--hash[cs[now]]))return;
		cs[now]=cs[v[m1]]+1;
		kt[now]=m1;hash[cs[now]]++;
		if(now!=S)now=v[pre[now]^1],flow=w[now];
	}
}
int main()
{
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%d%d",&n,&m);
		S=n-1;T=n;l=1;ans=0;
		memset(gs,0,sizeof(gs));
		memset(head,0,sizeof(head));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			if(y<x)swap(x,y);
			gs[x]++;gs[y]++;
			if(y==2){ans++;continue;}
			if(x==1)add(S,y-2,1,0);
			if(x==2)add(y-2,T,1,0);
			if(x>2)add(x-2,y-2,1,1);
		}
		sap();
		printf("%d ",m-ans);
		f.reset();f[0]=1;
		for(i=3;i<=n;i++)f|=f<<gs[i];
		for(i=m-gs[1];!f[i];i--);
		ans=m-gs[1]-i;
		for(i=m-gs[2];!f[i];i--);
		ans=min(ans,m-gs[2]-i);
		printf("%d\n",ans);
	}
}

4149: [AMPPZ2014]Global Warming

一位一位扫过去。。然后维护两个单调栈,然后扭一扭脖子即可。

#include<cstdio>
#include<algorithm>
#define N 500010
using namespace std;
int n,i,a[N],q[N],h[N],top,fro,pre[N],pra[N],sg,xx,ans,yy,j;
int main()
{
	scanf("%d",&n);sg=n+1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		for(;a[i]<a[q[top]]&⊤top--);
		pre[i]=q[top]+1;
		if(a[i]==a[q[top]]&&top)top--;
		if(sg>q[top])sg=n+1;
		q[++top]=i;
		for(;a[i]>a[h[fro]]&&fro;fro--);
		pra[i]=h[fro]+1;
		if(a[i]==a[h[fro]]&&fro)fro--;
		if(sg>h[fro])sg=n+1;
		h[++fro]=i;
		xx=lower_bound(h+1,h+fro+1,pre[i])-h;
		xx=max(pre[i],pra[h[xx]]);
		if(xx<sg)sg=xx;
		xx=lower_bound(q+1,q+top+1,pra[i])-q;
		xx=max(pra[i],pre[q[xx]]);
		if(xx<sg)sg=xx;
		if(i-sg+1>ans)ans=i-sg+1,yy=sg;
	}
	printf("%d %d\n",ans,yy);
}

4144: [AMPPZ2014]Petrol

考虑一条边。对于他两侧的点,找到最近的关键点,然后对这两个关键点建边。

之后跑kruskal即可。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define M 400010
using namespace std;
int n,s,m,v[M],ne[M],head[N],len[M],dis[N],pr[N],dad[N],an[N];
int c[N],l,i,x,y,z,j,T,a[N],b[N],f[N],heap[N],wz[N],ln,lls,u;
struct str{int x,y,z;}li[M];
int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);}
bool cmp1(str a,str b){return a.z<b.z;}
void add(int x,int y,int z)
{
	v[++l]=y;ne[l]=head[x];
	head[x]=l;len[l]=z;
}
void pushup(int x,int y)
{
	for(;x>>1&&dis[heap[x>>1]]<dis[y];x>>=1)
		heap[x]=heap[x>>1],wz[heap[x]]=x;
	heap[x]=y;wz[y]=x;
}
void pushdown(int x,int y)
{
	for(;x<<1<=ln;x=lls)
	{
		lls=x<<1;
		if(lls<ln&&dis[heap[lls|1]]<dis[heap[lls]])lls|=1;
		if(dis[heap[lls]]>=dis[heap[x]])break;
		heap[x]=heap[lls];wz[heap[x]]=x;
	}
	heap[x]=y;wz[y]=x;
}
void spfa()
{
	for(i=1;i<=n;i++)if(pr[i])
		pushup(++ln,i);
	for(;ln;)
	{
		u=heap[1];pushdown(1,heap[ln--]);wz[u]=0;
		for(i=head[u];i;i=ne[i])
			if(dis[u]+len[i]<dis[v[i]])
			{
				dis[v[i]]=dis[u]+len[i];pr[v[i]]=pr[u];
				if(!wz[v[i]])wz[v[i]]=++ln;
				pushup(wz[v[i]],v[i]);
			}
	}
}
bool cmp(int x,int y){return c[x]<c[y];}
int main()
{
	scanf("%d%d%d",&n,&s,&m);
	memset(dis,63,sizeof(dis));
	for(i=1;i<=s;i++)
	{
		scanf("%d",&c[i]);
		dis[c[i]]=0;
		pr[c[i]]=c[i];
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	spfa();
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		f[i]=i;
	}
	sort(f+1,f+T+1,cmp);l=0;
	for(i=1;i<=n;i++)
	{
		dad[i]=i;
		for(j=head[i];j;j=ne[j])
			if(pr[v[j]]>pr[i])
			{
				li[++l].x=pr[i];
				li[l].y=pr[v[j]];
				li[l].z=dis[i]+dis[v[j]]+len[j];
			}
	}
	sort(li+1,li+l+1,cmp1);j=1;
	for(i=1;i<=T;i++)
	{
		u=f[i];
		for(;li[j].z<=c[u]&&j<=l;j++)
			if(find(li[j].x)!=find(li[j].y))
				dad[dad[li[j].x]]=dad[li[j].y];
		an[u]=find(a[u])==find(b[u]);
	}
	for(i=1;i<=T;i++)
		an[i]?puts("TAK"):puts("NIE");
}

4145: [AMPPZ2014]The Prices

大力子集DP即可。

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,x,j,a[20],g[100010],f[100010],k;
int main()
{
	scanf("%d%d",&n,&m);
	memset(g,63,sizeof(g));
	g[0]=0;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		for(j=0;j<m;j++)
			scanf("%d",&a[j]);
		for(j=0;j<1<<m;j++)
		{
			f[j]=g[j]+x;
			for(k=0;k<m;k++)if(j>>k&1)
				if(f[j^(1<<k)]+a[k]<f[j])
					f[j]=f[j^(1<<k)]+a[k];
			if(g[j]>f[j])g[j]=f[j];
		}
	}
	printf("%d\n",g[(1<<m)-1]);
}

4152: [AMPPZ2014]The Captain

把x或y坐标相邻的点之间连边,然后跑最短路即可。加了堆优化跑蛮快的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define M 800010
using namespace std;
int n,i,dis[N],l,head[N],wz[N],heap[N];
int len[M],v[M],ne[M],ln,ssd,u;
struct cpx{int x,y;}a[N],b[N];
bool cmp(cpx a,cpx b)
{
	return a.x<b.x;
}
void add(int x,int y,int z)
{
	v[++l]=y;ne[l]=head[x];
	head[x]=l;len[l]=z;
	v[++l]=x;ne[l]=head[y];
	head[y]=l;len[l]=z;
}
void pushup(int x,int y)
{
	for(;(x>>1)&&dis[heap[x>>1]]>dis[y];x>>=1)
		heap[x]=heap[x>>1],wz[heap[x]]=x;
	heap[x]=y;wz[y]=x;
}
void pushdown(int x,int y)
{
	for(;(x<<1)<=ln;x=ssd)
	{
		ssd=x<<1;
		if(ssd<ln&&dis[heap[ssd|1]]<dis[heap[ssd]])ssd|=1;
		if(dis[heap[ssd]]>=dis[y])break;
		heap[x]=heap[ssd];wz[heap[x]]=x;
	}
	heap[x]=y;wz[y]=x;
}
void dij()
{
	memset(dis,63,sizeof(dis));
	dis[1]=0;pushup(ln=1,1);
	for(;heap[1]!=n;)
	{
		u=heap[1];pushdown(1,heap[ln--]);wz[u]=0;
		for(i=head[u];i;i=ne[i])
			if(dis[u]+len[i]<dis[v[i]])
			{
				dis[v[i]]=dis[u]+len[i];
				if(!wz[v[i]])wz[v[i]]=++ln;
				pushup(wz[v[i]],v[i]);
			}
	}
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&b[i].x);
		a[i].y=b[i].y=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	for(i=1;i<n;i++)
	{
		add(a[i].y,a[i+1].y,a[i+1].x-a[i].x);
		add(b[i].y,b[i+1].y,b[i+1].x-b[i].x);
	}
	dij();
	printf("%d\n",dis[n]);
}

4143: [AMPPZ2014]The Lawyer

直接求出每天最早的结束时间和最晚的开始时间然后比一比~

#include<cstdio>
#include<cstring>
#define N 25
using namespace std;
char ch;
int n,m,i,x,y,z,mi[N],mmi[N],ma[N],mma[N];
void read(int &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main()
{
	read(n);read(m);
	memset(mi,63,sizeof(mi));
	for(i=1;i<=n;i++)
	{
		read(x);read(y);read(z);
		if(y<mi[z])mi[z]=y,mmi[z]=i;
		if(x>ma[z])ma[z]=x,mma[z]=i;
	}
	for(i=1;i<=m;i++)
	{
		if(mi[i]<ma[i])
			printf("TAK %d %d\n",mmi[i],mma[i]);
		else puts("NIE");
	}
}

4146: [AMPPZ2014]Divisors

直接nlogn,调和级数。

#include<cstdio>
#define N 2000010
using namespace std;
int n,i,x,m,j;
long long ans,a[N];
char ch;
void read(int &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
} 
int main()
{
	read(n);
	for(i=1;i<=n;i++)
	{
		read(x);a[x]++;
		if(x>m)m=x;
	}
	for(i=m;i>=1;i--)
	{
		for(j=i<<1;j<=m;j+=i)
			ans+=a[i]*a[j];
		ans+=a[i]*(a[i]-1);
	}
	printf("%lld\n",ans);
}

3925: [Zjoi20150]地震后的幻想乡

考试的时候由于组合数乘里面了导致此题没调出来。。

终于收复失地,还跑最快蛤蛤。。大概就是子集DP一下就好了。。

由于不用多项式精度没有误差。。所以喽,很资磁!

#include<cstdio>
#define N 1024
using namespace std;
int n,m,S,V,x,y,g[N],gs[N],j,i,k,l;
double s[110][N],ans,tot,C[110][110],ss;
int main()
{
	scanf("%d%d",&n,&m);
	S=1<<n;V=S-1;gs[0]=-1;
	for(j=1;j<S;j++)
		gs[j]=gs[j>>1]+(j&1);
	for(i=0;i<=m;i++)C[0][i]=1;
	for(i=1;i<=m;i++)
		for(j=1;j<=i;j++)
			C[j][i]=C[j-1][i-1]+C[j][i-1];
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);x--;y--;
		for(j=0;j<S;j++)
			if((j>>x&1)&&(j>>y&1))g[j]++;
	}
	for(i=1;i<S;i++)
	{
		for(j=(i-1)&i;j>(i^j);j=(j-1)&i)
			for(k=gs[j];k<=g[j];k++)
				for(l=gs[i^j];l<=g[i^j];l++)
					s[k+l+1][i]+=s[k][j]*s[l][i^j]*C[k][k+l]*(g[i]-g[j]-g[i^j]);
		if(i!=V)for(j=gs[i];j<=g[i];j++)
			s[j][i]+=s[j-1][i]*(g[i]-j+1);
		if(!gs[i])s[0][i]=1;
	}
	ss=1;
	for(i=g[V];i>=gs[V];i--)
	{
		ans+=s[i][V]*i*ss;
		tot+=s[i][V]*ss;
		ss=ss*(g[V]-i+1);
	}
	printf("%.6lf\n",ans/tot/(m+1));
}

3998: [TJOI2015]弦论

后缀自动机模板题。T=1时在parent树上预处理出每个字串出现的次数。

然后统计出每个节点走下去一共有几种合法的接受状态。然后直接跑出第K大即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000010
using namespace std;
char s[N],ap[N];
int T,n,fail[N],son[26][N],wz[N],i,j,ch,tot,p,f[N],cur;
long long v[N],vp[N],k;
bool cmp(int x,int y)
{
	return wz[x]<wz[y];
}
int main()
{
	scanf("%s%d%lld",s+1,&T,&k);
	n=strlen(s+1);fail[0]=-1;tot=n;
	for(i=1;i<=n;i++)
	{
		ch=s[i]-'a';wz[i]=i;
		for(j=i-1;j>=0;j=fail[j])
		{
			if(son[ch][j])break;
			son[ch][j]=i;
		}
		if(j<0)fail[i]=0;else
		if(wz[j]+1==wz[son[ch][j]])
			fail[i]=son[ch][j];
		else
		{
			tot++;p=son[ch][j];
			wz[tot]=wz[j]+1;
			fail[tot]=fail[p];
			fail[i]=fail[p]=tot;
			for(;j>=0;j=fail[j])
			{
				if(son[ch][j]!=p)break;
				son[ch][j]=tot;
			}
			for(j=0;j<26;j++)
				son[j][tot]=son[j][p];
		}
	}
	for(i=1;i<=tot;i++)f[i]=i;
	sort(f+1,f+tot+1,cmp);
	for(i=tot;i>=1;i--)
	{
		if(f[i]<=n||(!T))v[f[i]]++;
		if(T)v[fail[f[i]]]+=v[f[i]];
		vp[f[i]]=v[f[i]];
		for(j=0;j<26;j++)
			vp[f[i]]+=vp[son[j][f[i]]];
	}
	v[0]=0;
	for(cur=i=0;k>v[cur];i++)
	{
		k-=v[cur];
		for(j=0;j<26;j++)
			if(k>vp[son[j][cur]])
				k-=vp[son[j][cur]];
			else break;
		cur=son[j][cur];ap[i]='a'+j;
	}
	printf("%s\n",ap);
}

3997: [TJOI2015]组合数学

求最大和上升子序列即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,i,j,g[1010],f[1010],T;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		memset(g,0,sizeof(g));
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%d",&f[j]);
				f[j]+=g[j+1];
			}for(j=m;j>=0;j--)
				g[j]=max(g[j],max(g[j+1],f[j]));
		}printf("%d\n",g[0]);
	}
}

3931: [CQOI2015]网络吞吐量

裸题。在最短路上跑网络流。

跑得奇慢无比,难道是我的姿势不对。。?

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e15
#define M 600010
#define N 1010
using namespace std;
int n,m,x,y,l,head[N],S,q[M],r,i,use[N];
int v[M],ne[M],max1;
int hash[N],now,cs[N],kt[N],T,flag,pre[N];
long long dis[N],fl[M],co[M],flow,ans,w[N],c;
void add(int x,int y,long long c,long long f)
{
	v[++l]=y;ne[l]=head[x];
	head[x]=l;fl[l]=f;co[l]=c;
	v[++l]=x;ne[l]=head[y];
	head[y]=l;fl[l]=0;co[l]=-c;
}
void spfa()
{
	memset(dis,63,sizeof(dis));dis[S]=0;
	for(q[l=r=1]=S;l<=r;l++)
	{
		for(i=head[q[l]],use[q[l]]=0;i;i=ne[i])
			if(dis[q[l]]+co[i]<dis[v[i]]&&fl[i])
			{
				dis[v[i]]=dis[q[l]]+co[i];
				if(!use[v[i]])use[v[i]]=1,q[++r]=v[i];
			}
	}
}
void sap()
{
    hash[0]=T;flow=INF;
    now=S;cs[0]=1e9;
    for(i=1;i<=T;i++)kt[i]=head[i];
    while(cs[S]<=T)
    {
        w[now]=flow;flag=0;
        for(i=kt[now];i;i=ne[i])
        if(fl[i]&&cs[now]==cs[v[i]]+1&&dis[v[i]]==dis[now]+co[i])
        {
            kt[now]=i;
            flow=min(flow,fl[i]);
            pre[now=v[i]]=i;flag=1;
            if(now==T)
            {
                ans+=flow;
                for(;now!=S;now=v[pre[now]^1])
                {
                    fl[pre[now]]-=flow;
                    fl[pre[now]^1]+=flow;
                }
                flow=w[now];
            }
            break;
        }
        if(flag)continue;max1=0;
        for(i=head[now];i;i=ne[i])
            if(fl[i]&&cs[v[i]]<cs[v[max1]]&&dis[v[i]]==dis[now]+co[i])
                max1=i;
        kt[now]=max1;hash[cs[now]]--;
        if(!hash[cs[now]])return;
        cs[now]=cs[v[max1]]+1;
        if(cs[now]<=T)hash[cs[now]]++;
        if(now!=S)now=v[pre[now]^1];flow=w[now];
    }
}
int main()
{
	scanf("%d%d",&n,&m);l=1;
	S=n+1;T=n<<1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%lld",&x,&y,&c);
		add(x+n,y,c,INF);
		add(y+n,x,c,INF);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&c);
		if(i<n)add(i,i+n,0,c);
	}
	add(n,T,0,INF);
	spfa();sap();
	printf("%lld\n",ans);
}

4001: [TJOI2015]概率论

打表找规律即可。用母函数比较复杂,大概是利用了广义二项式定理,然后结合卡特兰数即可推出。

#include<cstdio>
using namespace std;
double n;
int main()
{
	scanf("%lf",&n);
	printf("%.9lf\n",n*(n+1)/(4*n-2));
}

4011: [HNOI2015]落忆枫樱

有向图生成树计数。如果不考虑多余边就是除去零入度点每个点的入度的∏。

不合法状态就是从y连了一条链到x。考虑dp。f[i]表示从y走到这个点,所有边的总方案数。

因为每次转移的时候多确定了一条边。所以要把方案数除以转移过去的那个点的入度。

按照拓扑图顺序DP即可。

#include<cstdio>
#define mod 1000000007
#define N 100010
#define M 200010
using namespace std;
int n,m,x,y,i,a,b,q[N],v[M],ne[M],head[N],l,gs[N],r,j,wz[N],u;
long long tot,dis[N],B[N],A[N];
void add(int x,int y)
{
	v[++l]=y;ne[l]=head[x];head[x]=l;
}
long long powmod(long long x,int y)
{
	long long ans=1;
	for(;y;y>>=1,x=x*x%mod)
		if(y&1)ans=ans*x%mod;
	return ans;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);gs[b]++;
	}
	tot=1;
	for(i=1;i<=n;i++)
	{
		A[i]=gs[i]+(i==y);
		B[i]=powmod(A[i],mod-2);
		if(!A[i])q[++r]=i;
		else tot=tot*A[i]%mod;
	}
	for(l=1;l<=r;l++)
	{
		wz[q[l]]=l;
		for(j=head[q[l]];j;j=ne[j])
		{
			gs[v[j]]--;
			if(!gs[v[j]])q[++r]=v[j];
		}
	}
	dis[y]=tot%mod;
	for(i=wz[y];i<=n;i++)
	{
		u=q[i];dis[u]%=mod;
		(dis[u]*=B[u])%=mod;
		for(j=head[u];j;j=ne[j])
			dis[v[j]]+=dis[u];
	}
	tot-=dis[x];
	if(tot<0)tot+=mod;
	printf("%lld\n",tot);
}

3996: [TJOI2015]线性代数

把式子展开后就变成[tex]\sum_{1\leqslant i,j\leqslant n}^{ }a_{i}*a_{j}*b_{i,j}-\sum_{1\leqslant i\leqslant n}^{ }a_{i}*c_{i}[/tex]

然后这东西就是一个裸的网络流。建图跑即可。

#include<cstdio>
#include<algorithm>
#define INF 1e9
#define N 300010
#define M 3000010
using namespace std;
int n,S,T,i,j,l,hash[N],flow,now,cs[N],pre[N],ans;
int v[M],ne[M],head[N],fl[M],kt[N],w[N],flag,max1,x;
void add(int x,int y,int f)
{
	v[++l]=y;ne[l]=head[x];head[x]=l;fl[l]=f;
	v[++l]=x;ne[l]=head[y];head[y]=l;fl[l]=0;
}
void sap()
{
	hash[0]=T;flow=INF;
	now=S;cs[0]=1e9;
	for(i=1;i<=T;i++)kt[i]=head[i];
	while(cs[S]<=T)
	{
		w[now]=flow;flag=0;
		for(i=kt[now];i;i=ne[i])
		if(fl[i]&&cs[now]==cs[v[i]]+1)
		{
			kt[now]=i;
			flow=min(flow,fl[i]);
			pre[now=v[i]]=i;flag=1;
			if(now==T)
			{
				ans-=flow;
				for(;now!=S;now=v[pre[now]^1])
				{
					fl[pre[now]]-=flow;
					fl[pre[now]^1]+=flow;
				}
				flow=w[now];
			}
			break;
		}
		if(flag)continue;max1=0;
		for(i=head[now];i;i=ne[i])
			if(fl[i]&&cs[v[i]]<cs[v[max1]])
				max1=i;
		kt[now]=max1;hash[cs[now]]--;
		if(!hash[cs[now]])return;
		cs[now]=cs[v[max1]]+1;
		if(cs[now]<INF)hash[cs[now]]++;
		if(now!=S)now=v[pre[now]^1];flow=w[now];
	}
}
int main()
{
	scanf("%d",&n);
	S=n*n+n+1;T=S+1;l=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			scanf("%d",&x);
			add(i,i*n+j,INF);
			add(j,i*n+j,INF);
			add(i*n+j,T,x);
			ans+=x;
		}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		add(S,i,x);
	}
	sap();
	printf("%d\n",ans);
}

排名不按做题顺序


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee