hdu 4294 第一发SAP
#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;
int head;
int dep,gap;
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.u=u;
edge.v=v;
edge.cap=w;
edge.flow=0;
edge.next=head;
head=tol++;
edge.u=v;
edge.v=u;
edge.cap=0;
edge.flow=0;
edge.next=head;
head=tol++;
}
void bfs()
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap=1;
queue<int> q;
int u,v,i;
q.push(last);dep=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!=-1) continue;
q.push(v);
dep=dep+1;
++gap];
}
}
}
int sap()
{
int max_flow=0,i,u,v;
bfs();
int cur;
int S;
int top=0;
for(i=0;i<=last;i++)
cur=head;
u=0;
while(dep<=last)
{
if(u==last)
{
int temp=INF;
int inser;
for(i=0;i<top;i++)
if(temp>edge].cap-edge].flow)
{
temp=edge].cap-edge].flow;
inser=i;
}
for(i=0;i<top;i++)
{
edge].flow+=temp;
edge^1].flow-=temp;
}
max_flow+=temp;
top=inser;
u=edge].u;
}
if(u!=last&&gap-1]==0) break;
for(i=cur;i!=-1;i=edge.next)
if(edge.cap>edge.flow&&dep==dep.v]+1)
break;
if(i!=-1)
{
cur=i;
S=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.v])
{
mi=dep.v];
cur=i;
}
}
--gap];
dep=mi+1;
++gap];
if(u!=0) u=edge].u;
}
}
return max_flow;
}
int main()
{
int i,j,n,F,D,u,v,w;
char s;
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=='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=='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,不知道什么原因
页:
[1]