ACM

/
ID:qcx97811
LANG:C
TASK:H
/
#include
#include
#include
#include
/还有一个修改没加/
typedef struct//线段树的结构体
{//l表示左端点 r右端点 max表示这一段的最大值 min表示这一段的最小值
int l,r
int max,min
}Tree
Tree node[5000064];//4倍
void init_node(int idx,int _l,int _r)
{//初始化线段树
int mid
node[idx].l=_l//这里不管怎样都要赋值,确定边界
node[idx].r=_r
if(_l == _r)
{//如果到了底层了直接返回
return ;
}
mid=(_l+_r)>>1;
init_node(2idx,_l,mid);//初始化左子树
init_node(2idx+1,mid+1,_r);//初始化右子树
}
void insert(int idx,int _l,int _r,int val)
{//插入一个值
int mid
if(_l<=node[idx].l & _r>=node[idx].r)
{//如果区域覆盖这棵树就直接改变这棵树就行了 不改变子树的信息
node[idx].min=node[idx].max=val
return ;
}
if(_r<=node[2idx].r)
{//插入左子树
insert(2idx,_l,_r,val);
//更新该区域的最大最小值
if(node[2idx].max > node[idx].max)
node[idx].max=node[2idx].max
if(node[2idx].min < node[idx].min)
node[idx].min=node[2idx].min
}
else
{
if(_l>=node[2idx+1].l)
{//插入右子树
insert(2idx+1,_l,_r,val);
//更新该区域的最大最小值
if(node[2idx+1].max>node[idx].max)
node[idx].max=node[2idx+1].max
if(node[2idx+1].min<node[idx].min)
node[idx].min=node[2idx+1].min
}
else
{
//插入左子树和右子树
insert(2idx,_l,node[2idx].r,val);
insert(2idx+1,node[2idx+1].l,_r,val);
//更新该区域的最大最小值
if(node[2idx].max > node[idx].max)
node[idx].max=node[2idx].max
if(node[2idx].min < node[idx].min)
node[idx].min=node[2idx].min
if(node[2idx+1].max > node[idx].max)
node[idx].max=node[2idx+1].max
if(node[2idx+1].min < node[idx].min)
node[idx].min=node[2idx+1].min
}
}
}
int query_max(int idx,int _l,int _r)
{//求_l到_r区间的最大值
int max,max1
if(_l<=node[idx].l & _r>=node[idx].r)//如果覆盖这个区域 直接返回
return node[idx].max
if(_r<=node[2idx].r)
{//返回左子树的最大值
return query_max(2idx,_l,_r);
}
else
{
if(_l>=node[2idx+1].l)//返回右子树的最大值
return query_max(2idx+1,_l,_r);
//返回左子树和右子树中最大值的最大值
max=query_max(2idx,_l,node[2idx].r);
max1=query_max(2idx+1,node[2idx+1].l,_r);
if(max>max1)
return max
else
return max1
}
}
int query_min(int idx,int _l,int _r)
{//类似上面的query_max
int min,min1
if(_l<=node[idx].l & _r >=node[idx].r)
return node[idx].min
if(_r<=node[2idx].r)
return query_min(2idx,_l,_r);
else
{
if(_l>=node[2idx+1].l)
{
return query_min(2idx+1,_l,_r);
}
else
{
min=query_min(2idx,_l,node[2idx].r);
min1=query_min(2idx+1,node[2*idx+1].l,_r);
if(min<min1)
return min
else
return min1
}
}
}

/
ID:qcx97811
LANG:C
TASK:24-3/NKU_2123
/
#include
#include
#include
#include
#include

int n,m
int graph[360][360],c[360][360];
int d[360],gap[360],maxflow
void sap()
{
int u,v
int q[360],low[360];//这里的数组大小是顶点的个数+i
int tmp,front,rear
maxflow=0
//bfs
q[rear=0]=n2+1//这里是汇点
front=-1
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
d[2n+1]=0//这里是汇点的层次度为0
while(front < rear)
{
u=q[++front];
for(v=0v<=2n+1;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]=0//这里是起点
low[0]=INT_MAX//这里记得赋值 无穷大
while(d[0]<2(1+n))//这里的2(n+1)是如果所有的点是一条链的时候源点的标号+1
{//这里是起点的层次信息
u=q[tmp];
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
if(graph[u][v]>0 & d[v]+1==d[u])
break
}
if(2(n+1)==v)//这里v==上面for循环的上界+1
{//此点出度为0
gap[d[u]]–
if(gap[d[u]] == 0)
break
d[u]=2n+2//这里应该赋值为一个无穷大
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
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==2n+1)//这里的n2+1是顶点的最大标号
{//找到一条增广路
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
}
}
}
}
void output()
{
char used[360];
int i,j,now
memset(used,0,sizeof(used));
for(i=1i<=n;i++)
{
if(0==used[i])
{
printf(“%d”,i);
now=i
while(1)
{
used[now]=1
for(j=1j<=c[now][0];j++)
{
if(0==used[c[now][j]]&0==graph[now][c[now][j]])
{
printf(“ %d”,c[now][j]-n);
used[c[now][j]]=1
break
}
}
if(c[now][0]+1==j)
break
else
now=c[now][j]-n;
if(1==used[now])
break
}
printf(“\n“);
}
}
printf(“%d\n“,n-maxflow);
}
int main(void)
{
freopen(“24-3.in”,“r”,stdin);
freopen(“24-3.out”,“w”,stdout);
int i,s,e,j
scanf(“%d%d”,n,&m);
memset(graph,0,sizeof(graph));
memset(c,0,sizeof(c));
for(i=0i<m;i++)
{
scanf(“%d%d”,s,&e);
graph[s][n+e]=1
c[s][++c[s][0]]=n+e
}
for(i=1i<=n;i++)
{
graph[0][i]=1
graph[n+i][2n+1]=1
}
#if 0
for(i=0;i<2*(n+1);i++)< span="">
{
for(j=0;j<2*(n+1);j++)< span="">
printf(“(%d,%d:%d) “,i,j,graph[i][j]);
printf(“\n”);
}
#endif
#if 1
sap();
output();
#endif
return 0
}

/
ID:qcx97811
LANG:C
TASK:ditch
/
#include
#include
#include
#include
int graph[206][206],d[206],gap[206];
int N,M,maxflow

void bfs()
{
int i,j
int q[206];
int front,rear
front = -1
q[rear=0]=M
memset(d,-1,sizeof(d));
d[M]=0
memset(gap,0,sizeof(gap));
gap[0]=1
while(front < rear)
{
i = q[++front];
for(j = 1j <= M;j++)
{
if(-1 == d[j] & graph[j][i] > 0)
{
d[j] = d[i]+1
q[++rear] = j
gap[d[j]]++
}
}
}
}
void sap()
{
int i,j
int top,q[206],low[206];
bfs();
#if 0
printf(“%d %d %d %d\n”,d[1],d[2],d[3],d[4]);
printf(“——–after bfs\n”);
#endif
top=0
low[0]=INT_MAX
q[top]=1
while(d[1] < M)
{
for(i = 1i <= M;i++)
{
if(graph[q[top]][i] > 0 & d[i]+1==d[q[top]])
{
q[++top]=i
low[top]=graph[q[top-1]][i];
if(low[top] > low[top-1])//到当前点的增广流的最大值
low[top]=low[top-1];
break
}
}
if(i != (M+1))//注意这里是M+1和上面的for循环的出口对应 应该是for循环的最大值+1
{
if(M == q[top])//如果已经找到一条增广路
{
for(i = 0i < top;i++)
{//更新残留网络
graph[q[i]][q[i+1]] -= low[top];
graph[q[i+1]][q[i]] += low[top];
}
maxflow += low[top];//更改结果
top = 0//重新从源点开始找
}
}
else
{
j = q[top];
gap[d[j]]–//这个点对应的层次的点的个数-1
if(gap[d[j]] == 0)//如果-1之后==0那么就出现了断层,可以直接退出了,至于证明这个应该不难吧.
{
break
}
d[j] = M+1
for(i = 1i <= M;i++)
{
if(graph[j][i] > 0 & d[i]+1 < d[j] && d[i] >= 0)
{//注意这里的d[i] >= 0因为并不是所有的点都在层次图中
d[j]=d[i]+1
}
}
gap[d[j]]++//对应的点的层次的点的个数+1
if(top>0)//如果不是源点就退到前一个顶点
top–
}
}
return ;
}

int main(void)
{
freopen(“ditch.in”,“r”,stdin);
freopen(“ditch.out”,“w”,stdout);
int i,s,e,c
scanf(“%d%d”,N,&M);
memset(graph,0,sizeof(graph));
for(i = 0i < N;i++)
{
scanf(“%d%d%d”,s,&e,&c);
graph[s][e] += c
}
sap();
printf(“%d\n“,maxflow);
return 0
}

/
LANG:C
TASK:
ID:qcx97811
/
#include
#include
#include

int graph[106][106],pre[106];
int N,M,maxflow

int bfs()
{
int i,j
int q[206];
int front,rear
memset(pre,-1,sizeof(pre));
front = rear = -1
q[++rear] = 0
while(front < rear)
{
i = q[++front];
for(j = 0j <= (N+1);j++)
{
if(-1 == pre[j] & graph[i][j] > 0)
{
pre[j] = i
rear++
q[rear] = j
if(j == (N+1))
return 1
}
}
}
return 0
}
void max_flow()
{
int i,j,add
maxflow = 0
while(0 != (add = bfs()))
{
add = 10000006
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
if(graph[j][i] < add)
add = graph[j][i];
}
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
graph[j][i] -= add
graph[i][j] += add
}
maxflow += add
}
}
int main(void)
{
freopen(“24-1.in”,“r”,stdin);
freopen(“24-1.out”,“w”,stdout);
int i,j,s,e
scanf(“%d%d”,M,&N);
memset(graph,0,sizeof(graph));
while(1)
{
scanf(“%d%d”,s,&e);
if((-1 == s) & (-1 == e))
break
if(s > e)
{//确定是从一个方向流往另外一个方向
i = s;
s = e
e = i
}
graph[s][e] = 1
}
for(i = 1i <= M;i++)//超级源点
graph[0][i] = 1
for(i = M+1i <= N;i++)//超级汇点
graph[i][N+1] = 1
max_flow();
if(0 == maxflow)
{
printf(“No Solution\n“);
}
else
{
printf(“%d\n“,maxflow);
for(i = 1i <= M;i++)
{
for(j = (M+1);j <= N;j++)
{
if(graph[j][i] == 1)
{
printf(“%d %d\n“,i,j);
//这里的输出注意下 附数据如下
//2 4
//1 3
//1 4
//2 3
//-1 -1
}
}
}
}
return 0
}