Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:福利

Posted by OZY123 at 2016-02-16 11:48:24 on Problem 1966
In Reply To:福利 Posted by:OZY123 at 2016-02-16 11:48:18
```#include<cstdio>
#include<cstring>
const int N=500;
const int MAX=999999999;
int n,m;
struct qq
{
int x,y;
int other;
int z,last;
};
qq s[N*N];
qq k[N*N];
int num,last[N];
int st1,ed1;
int h[N];
int q[N];//循环队列
int min;
int init1 (int x,int y,int z)
{
num++;
s[num].x=x;
s[num].y=y;
s[num].z=z;
s[num].last=last[x];
last[x]=num;
return num;
}
void init(int x,int y,int z)
{
int num1=init1(x,y,z),num2=init1(y,x,0);
s[num1].other=num2;
s[num2].other=num1;
}
{
num=0;
memset(last,-1,sizeof(last));
for (int u=0;u<n;u++)
init(u+n,u,1);
return ;
}
bool bt ()
{
memset(h,0,sizeof(h));
int st=1,ed=2;
q[st]=st1;h[st1]=1;
while (st!=ed)
{
int x=q[st];
for (int u=last[x];u!=-1;u=s[u].last)
{
int y=s[u].y;
if (s[u].z>0&&h[y]==0)
{
h[y]=h[x]+1;
q[ed]=y;
ed++;
if (ed>=N) ed=1;
}
}
st++;
if (st>=N) st=1;
}
if (h[ed1]==0) return false;
return true;
}
int min1 (int x,int y)
{
return x<y?x:y;
}
int find (int x,int f)
{
if (x==ed1) return f;
int s1=0,t;
for (int u=last[x];u!=-1;u=s[u].last)
{
int y=s[u].y;
if (s[u].z>0&&h[y]==(h[x]+1)&&s1<f)
{
t=find(y,min1(s[u].z,f-s1));
//if (t!=MAX) printf("%d %d %d %d\n",x,s[u].x,s[u].y,s[u].z);
s1+=t;
s[u].z-=t;
s[s[u].other].z+=t;
}
}
if (s1==0) h[x]=0;
return s1;
}
void check (int x,int y)
{
int ans=0;
st1=x;
ed1=y+n;
while (bt()==true)
{
ans=ans+find(st1,MAX);
if (ans>=min) return ;
}
min=ans;
return ;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
if (n == 0) { printf("0\n"); continue; }
if (n == 1) { printf("1\n"); continue; }
if (m == 0) { printf("0\n"); continue; }
for (int u=1;u<=m;u++)
{
while (getchar()!='(');
int x,y;
scanf("%d,%d)",&x,&y);
init(y,x+n,MAX);
init(x,y+n,MAX);
}
for (int u=1;u<=num;u++) k[u]=s[u];
min=MAX;
for (int u=0;u<n;u++)//枚举起点
{
for (int i=0;i<n;i++)//枚举终点
{
if (u==i) continue;
for (int j=1;j<=num;j++) s[j]=k[j];
check(u,i);
}
}
if (min==MAX) min=n;
printf("%d\n",min);
}
return 0;
}```

Followed by: