题意：
给定带有源点S和汇点T的n个点m条边的带权有向图， 该图有若干S-T最小割，要求找到割的边数最少的最小割，输出这个最少边数。
数据范围：n<=200，m<=1000，边权<=255
解法：
假设图中共m条边
,
将图中的每条边边权x变为x
*(m
+1)+1,
然后计算最小割maxflow
,最小割的最少边数为maxflow
%(m
+1).
我自己理解的原理
(不保证正确
):
如果将每条边的边权乘上一个数p
,
显然现在最小割也为原来的p倍
,
如果将每条边的边权乘上一个数p之后再加
1,
那么现在最小割就是原来的p倍加上边数
.
最小割多出来的边数就是最少边数
.
(巧妙的利用了权值的影响
,妙啊
)
为什么要乘上p呢
?因为要避免乘上p之后影响整个图的最小割
.
一般取p
=m
+1,刚好为图的边数
+1,
因为图在形成一条链的时候
,一共是
+m
,要取的比m大才不影响
,
取太大乘起来可能会爆
,所以一般取m
+1最合适
.
code：
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int maxm
=1e6+5;
struct Dinic
{
static const int DN
=1e4+5;
static const int DM
=1e5+5;
static const ll inf
=1e16;
int head
[DN
],nt
[DM
],to
[DM
],tot
;
ll w
[DM
];
int d
[maxm
];
ll maxflow
;
int st
,ed
;
int n
;
bool bfs(){
queue
<int>q
;
q
.push(st
);
for(int i
=1;i
<=n
;i
++)d
[i
]=0;
d
[st
]=1;
while(!q
.empty()){
int x
=q
.front();q
.pop();
for(int i
=head
[x
];i
;i
=nt
[i
]){
int v
=to
[i
];
if(w
[i
]&&!d
[v
]){
d
[v
]=d
[x
]+1;
q
.push(v
);
if(v
==ed
)return 1;
}
}
}
return 0;
}
ll
dfs(int x
,ll flow
){
if(x
==ed
)return flow
;
ll res
=flow
;
for(int i
=head
[x
];i
;i
=nt
[i
]){
int v
=to
[i
];
if(w
[i
]&&d
[v
]==d
[x
]+1){
int k
=dfs(v
,min(res
,w
[i
]));
w
[i
]-=k
;
w
[i
^1]+=k
;
res
-=k
;
if(!k
)d
[v
]=-1;
if(!res
)break;
}
}
return flow
-res
;
}
ll
dinic(){
while(bfs()){
maxflow
+=dfs(st
,inf
);
}
return maxflow
;
}
void init(){
for(int i
=0;i
<=n
;i
++)head
[i
]=0;
tot
=1;
maxflow
=0;
}
void add(int x
,int y
,ll z
){
tot
++;nt
[tot
]=head
[x
];head
[x
]=tot
;to
[tot
]=y
;w
[tot
]=z
;
}
void add2(int x
,int y
,ll z
){
add(x
,y
,z
);
add(y
,x
,0);
}
}D
;
int n
,m
;
signed main(){
int T
;cin
>>T
;
while(T
--){
scanf("%d%d",&n
,&m
);
D
.n
=n
;
D
.init();
scanf("%d%d",&D
.st
,&D
.ed
);
for(int i
=1;i
<=m
;i
++){
int a
,b
,c
;scanf("%d%d%d",&a
,&b
,&c
);
c
=c
*(m
+1)+1;
D
.add2(a
,b
,c
);
}
ll ans
=D
.dinic()%(m
+1);
printf("%lld\n",ans
);
}
return 0;
}
