hdu 4294 第一发SAP

hjkn

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=0x7f7f7f7f;
const int maxn=10008;
struct fuck{
int u,v,flow,cap,next;
}edge[maxn<<4];
int head[maxn];
int dep[maxn],gap[maxn];
int tol;
int last;
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
int scan()  
{  
int res = 0, ch, flag = 0;  
if((ch = getchar()) == '-')             //判断正负  
flag = 1;  
else if(ch >= '0' && ch <= '9')           //得到完整的数  
res = ch - '0';  
while((ch = getchar()) >= '0' && ch <= '9' )  
res = res * 10 + ch - '0';  
return flag ? -res : res;  
}  
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol].cap=w;
edge[tol].flow=0;
edge[tol].next=head;
head=tol++;
edge[tol].u=v;
edge[tol].v=u;
edge[tol].cap=0;
edge[tol].flow=0;
edge[tol].next=head[v];
head[v]=tol++;
}
void bfs()
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=1;
queue<int>    q;
int u,v,i;
q.push(last);dep[last]=0;
while(!q.empty())
{
u=q.front();q.pop();
for(i=head;i!=-1;i=edge.next)
{
v=edge.v;
if(edge.cap!=edge.flow||dep[v]!=-1)    continue;
q.push(v);
dep[v]=dep+1;
++gap[dep[v]];
}
}
}
int sap()
{
int max_flow=0,i,u,v;
bfs();   
int cur[maxn];
int S[maxn];
int top=0;
for(i=0;i<=last;i++)
cur=head;
u=0;
while(dep[0]<=last)
{
if(u==last)
{
int temp=INF;
int inser;
for(i=0;i<top;i++)
if(temp>edge[S].cap-edge[S].flow)
{
temp=edge[S].cap-edge[S].flow;
inser=i;
}
for(i=0;i<top;i++)
{
edge[S].flow+=temp;
edge[S^1].flow-=temp;
}
max_flow+=temp;
top=inser;
u=edge[S[top]].u;
}
if(u!=last&&gap[dep-1]==0)    break;
for(i=cur;i!=-1;i=edge.next)
if(edge.cap>edge.flow&&dep==dep[edge.v]+1)
break;
if(i!=-1)
{
cur=i;
S[top++]=i;
u=edge.v;
}
else
{
int mi=last+1;
for(i=head;i!=-1;i=edge.next)
{
if(edge.cap==edge.flow)    continue;
if(mi>dep[edge.v])
{
mi=dep[edge.v];
cur=i;
}
}
--gap[dep];
dep=mi+1;
++gap[dep];
if(u!=0)    u=edge[S[--top]].u;
}
}
return max_flow;
}
int main()
{
int i,j,n,F,D,u,v,w;
char s[maxn];
while(scanf("%d%d%d",&n,&F,&D)==3)
{
init();
for(i=1;i<=F;i++)
{
scanf("%d",&w);
//w=scan();
addedge(0,i,w);
}
last=F+D+(n<<1)+1;
for(i=1;i<=D;i++)
{
scanf("%d",&w);
//w=scan();
addedge(i+F,last,w);
}
for(i=1;i<=n;i++)
{
scanf("%s",s);
int id=(i<<1);
for(j=0;j<F;j++)
if(s[j]=='Y')
addedge(j+1,id-1+F+D,1);
}
for(i=1;i<=n;i++)
{
scanf("%s",s);
int id=(i<<1);
for(j=0;j<D;j++)
if(s[j]=='Y')
addedge(id+F+D,j+1+F,1);
}
for(i=1;i<=n;i++)
{
int id=(i<<1);
addedge(id-1+F+D,id+F+D,1);
}
printf("%d\n",sap());
}
return 0;
}
　　
　　弱参考了几位巨巨的SAP代码，C++171MS,G++TLE.....
　　貌似别人的DINIC G++ 600多MS过，C++也跑600多MS,不知道什么原因