USACO 4.4.2 Pollutant Control
中文题目
这题最小割的模型是比较好明白的,但是对于剩下的两个输出就比较难搞了,也就是割边最少和序号最小.后来问了下一个同学,他说对每一条边(E+1)再+1.这样就能得到割边最少的最小割集了,一想还真是,因为割边的最小集加的最少嘛.但是我想了下可以直接+1么？我的理解是1001之后更好算一些,*1001再+1的话maxflow就直接用修改后的maxflow/1001就行了,然后割边集就等于修改后的maxflow%1001.剩下的就是怎么按顺序输出了.这里可以按输入顺序一次一次枚举,去掉当前边,然后最大流,如果当前边+当前最大流==原来最大流的话,就输出当前边,当然可以修改总的最大流或者用一个变量记录已经输出量多少条边:
我的代码如下:
/
ID:qcx97811
LANG:C
TASK:milk6
/
#include
#include
#include
#include
long long n,m,maxflow
long long graph[36][36];
long long se[1006][3];//se[i][0]边的起点 se[i][1]边的终点se[i][2]表示权值
long long d[36],gap[36];
void sap()
{//sap求最大流
long long u,v
long long q[36],low[36];
long long tmp,front,rear
maxflow=0
//bfs
q[rear=0]=n;//这里是汇点
front=-1
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
d[n]=0
while(front < rear)
{
u=q[++front];
for(v=1v<=n;v++)
{
if((-1==d[v])&(graph[v][u]>0))
{//这里是graph[v][u]不是graph[u][v]!!!
q[++rear]=v
d[v] = d[u]+1
gap[d[v]]++
}
}
}
//sap
q[tmp=0]=1
low[0]=INT_MAX//这里记得赋值
while(d[1]<n)
{
u=q[tmp];
for(v=1v<=n;v++)
{
if(graph[u][v]>0 & d[v]+1==d[u])
break
}
if((n+1)==v)
{//此点出度为0
gap[d[u]]–
if(gap[d[u]] == 0)
break
d[u]=n+1
for(v=1v<=n;v++)
{
if(graph[u][v] > 0 & d[v] >=0 && d[v]+1<d[u])
d[u]=d[v]+1
}
gap[d[u]]++
if(tmp>0)
tmp–
}
else
{
q[++tmp]=v
low[tmp]=graph[u][v];
if(low[tmp-1]<low[tmp])
low[tmp]=low[tmp-1];
if(v==n)
{//找到一条增广路
maxflow+=low[tmp];
for(u=0u<tmp;u++)
{//改变残留网络
front = q[u];
rear = q[u+1];
graph[front][rear] -= low[tmp];
graph[rear][front] += low[tmp];
}
tmp=0
}
}
}
}
int main(void)
{
freopen(“milk6.in”,“r”,stdin);
freopen(“milk6.out”,“w”,stdout);
int i
long long s,e,c
long long u,v,front,rear
int used[36];
scanf(“%d%d”,n,&m);
memset(graph,0,sizeof(graph));
for(i=0i<m;i++)
{
scanf(“%lld%lld%lld”,s,&e,&c);
graph[s][e] += 1001c+1
se[i][0]=s;
se[i][1]=e
se[i][2]=c1001+1//这里必须是1001c+1不然可能会出现输出不在割边里面的边
}
sap();
memset(used,0,sizeof(used));
d[rear=0]=1
front=-1
used[1]=1
while(front<rear)
{
u=d[++front];
for(v=1v<=n;v++)
{
if(0 == used[v]& graph[u][v] > 0)
{
d[++rear]=v
used[v]=1
}
}
}
front=maxflow//这个记录当前最大流是为了后面求割边集
u = maxflow/1001//原图最大流
v = maxflow-1001u//割边集的大小
maxflow=u
printf(“%lld %lld\n“,maxflow,v);
for(u=0u<m&v;u++)
{
memset(graph,0,sizeof(graph));
for(i=0i<m;i++)
{
graph[se[i][0]][se[i][1]]+=se[i][2];
}
graph[se[u][0]][se[u][1]] -= se[u][2];
sap();
if(se[u][2]+maxflow==front)
{
printf(“%lld\n“,u+1);
v–
}
}
return 0
}
ID:qcx97811
LANG:C
TASK:milk6
/
#include
#include
#include
#include
long long n,m,maxflow
long long graph[36][36];
long long se[1006][3];//se[i][0]边的起点 se[i][1]边的终点se[i][2]表示权值
long long d[36],gap[36];
void sap()
{//sap求最大流
long long u,v
long long q[36],low[36];
long long tmp,front,rear
maxflow=0
//bfs
q[rear=0]=n;//这里是汇点
front=-1
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
d[n]=0
while(front < rear)
{
u=q[++front];
for(v=1v<=n;v++)
{
if((-1==d[v])&(graph[v][u]>0))
{//这里是graph[v][u]不是graph[u][v]!!!
q[++rear]=v
d[v] = d[u]+1
gap[d[v]]++
}
}
}
//sap
q[tmp=0]=1
low[0]=INT_MAX//这里记得赋值
while(d[1]<n)
{
u=q[tmp];
for(v=1v<=n;v++)
{
if(graph[u][v]>0 & d[v]+1==d[u])
break
}
if((n+1)==v)
{//此点出度为0
gap[d[u]]–
if(gap[d[u]] == 0)
break
d[u]=n+1
for(v=1v<=n;v++)
{
if(graph[u][v] > 0 & d[v] >=0 && d[v]+1<d[u])
d[u]=d[v]+1
}
gap[d[u]]++
if(tmp>0)
tmp–
}
else
{
q[++tmp]=v
low[tmp]=graph[u][v];
if(low[tmp-1]<low[tmp])
low[tmp]=low[tmp-1];
if(v==n)
{//找到一条增广路
maxflow+=low[tmp];
for(u=0u<tmp;u++)
{//改变残留网络
front = q[u];
rear = q[u+1];
graph[front][rear] -= low[tmp];
graph[rear][front] += low[tmp];
}
tmp=0
}
}
}
}
int main(void)
{
freopen(“milk6.in”,“r”,stdin);
freopen(“milk6.out”,“w”,stdout);
int i
long long s,e,c
long long u,v,front,rear
int used[36];
scanf(“%d%d”,n,&m);
memset(graph,0,sizeof(graph));
for(i=0i<m;i++)
{
scanf(“%lld%lld%lld”,s,&e,&c);
graph[s][e] += 1001c+1
se[i][0]=s;
se[i][1]=e
se[i][2]=c1001+1//这里必须是1001c+1不然可能会出现输出不在割边里面的边
}
sap();
memset(used,0,sizeof(used));
d[rear=0]=1
front=-1
used[1]=1
while(front<rear)
{
u=d[++front];
for(v=1v<=n;v++)
{
if(0 == used[v]& graph[u][v] > 0)
{
d[++rear]=v
used[v]=1
}
}
}
front=maxflow//这个记录当前最大流是为了后面求割边集
u = maxflow/1001//原图最大流
v = maxflow-1001u//割边集的大小
maxflow=u
printf(“%lld %lld\n“,maxflow,v);
for(u=0u<m&v;u++)
{
memset(graph,0,sizeof(graph));
for(i=0i<m;i++)
{
graph[se[i][0]][se[i][1]]+=se[i][2];
}
graph[se[u][0]][se[u][1]] -= se[u][2];
sap();
if(se[u][2]+maxflow==front)
{
printf(“%lld\n“,u+1);
v–
}
}
return 0
}
