啊哈磊_编程从这里起步
标题:
12182 题解-草地排水
[打印本页]
作者:
code001
时间:
2019-1-27 18:07
标题:
12182 题解-草地排水
作为一个网络流的题目
这个题目严重缺失属于网络流的威风……
广搜其实应该也可以……
emmm关键是添柴的数据太水了
话不多说放代码
#include<iostream>
#include<cstdio>
#include<cstring>
int n,m,mi,i,l,r,x,y,z,c[505][505],f[505][505],q[505],flag;
struct note{int p;int d;}a[20000];
int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d %d %d",&x,&y,&z);
c[x][y]=c[x][y]+z;
}
flag=1;
while(flag!=0)
{
flag=0;
for(i=1;i<=m;i++)
q[i]=1;
l=0;
r=1;
a[1].p=0;
a[1].d=1;
while(l<r)
{
l++;
x=a[l].d;
for(i=1;i<=m;i++)
{
if(q[i]&&(c[x][i]>f[x][i]||f[i][x]>0))
{
q[i]=0;
r++;
a[r].d=i;
a[r].p=l;
if(i==m)
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
if (flag==0)
break;
mi=999999999;
i=r;
while (a[i].p!=0)
{
x=a[i].d;
y=a[a[i].p].d;
if(c[y][x]>f[y][x]&&c[y][x]-f[y][x]<mi)
mi=c[y][x]-f[y][x];
if(f[x][y]>0&&f[x][y]<mi)
mi=f[x][y];
i=a[i].p;
}
i=r;
while(a[i].p!=0)
{
x=a[i].d;
y=a[a[i].p].d;
if(c[y][x]>f[y][x])
f[y][x]=f[y][x]+mi;
if(f[x][y]>0)
f[x][y]=f[x][y]-mi;
i=a[i].p;
}
}
int ans=0;
for(i=1;i<=n;i++)
ans=ans+f[1][i];
printf("%d",ans);
return 0;
}
复制代码
作者:
Forinser
时间:
2019-1-29 09:43
是啊
现在是各种模式做
一个A+B都可以用珂朵莉树做,各种神仙代码QAQ
作者:
code001
时间:
2019-1-29 17:58
Forinser 发表于 2019-1-29 09:43
是啊
现在是各种模式做
一个A+B都可以用珂朵莉树做,各种神仙代码QAQ
添柴的数据是真的水,都不知道怎么回事
作者:
lyt0707
时间:
2019-1-29 17:59
是的,lca用dfs都能水过
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2