题意:有n个点和m条有向边构成的网络。每条边有两个花费:
d:毁坏这条边的花费
b:重建一条双向边的花费
寻找这样两个点集,使得点集s到点集t满足 毁坏全部S到T的路径的费用和 > 毁坏全部T到S的路径的费用和 + 重建这些T到S的双向路径的费用和。
思路1:
然后这个无源汇带上下界网络流的可行流问题的求解方法见
建图就是上面说的那样啦~最后推断有没有可行流就是求一下我们所构造的这个新的网络的最大流~然后推断一下这个最大流是否满流~(即推断最大流是否和附加源点的流出总量相等~~)
code:
#include
#include
#include
#include
#include
#include
#include
#include
思路2:
阔以试想~假设对于全部单一的一个点组成的集合S来说,都不能满足
S到T的路径的费用和 > 毁坏全部T到S的路径的费用和 + 重建这些T到S的双向路径的费用和 的话,那么随意的点的集合构成的S集合也一定并不能满足上述条件~~~反之假设存在集合满足上述条件的话,就一定存在单一的点满足上述条件~~~~
这样我们事实上仅仅用枚举点然后推断就好啦。。。。。
Orz。。。
code:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 205;
int n, m;
int D[maxn][maxn], B[maxn][maxn];
vector in[maxn], out[maxn];
void init(){
for(int i = 0; i < maxn; i++){
in[i].clear();
out[i].clear();
}
memset(D,0,sizeof(D));
memset(B,0,sizeof(B));
scanf("%d%d",&n,&m);
int u, v, dd, bb;
for(int i = 1; i <= m; i++){
scanf("%d%d%d%d",&u,&v,&dd,&bb);
out[u].push_back(v);
in[v].push_back(u);
D[u][v] = dd;
B[u][v] = bb;
}
}
bool deal(int u){
int x = 0;
for(int i = 0; i < in[u].size(); i++){
int v = in[u][i];
x += D[v][u];
}
int y = 0;
for(int i = 0; i < out[u].size(); i++){
int v = out[u][i];
y = y + D[u][v] + B[u][v];
}
if(y < x) return true;
return false;
}
void solve(){
for(int i = 1; i <= n; i++){
if(deal(i)){
printf("unhappy\n");
return;
}
}
printf("happy\n");
}
int main(){
int t;
int cas = 0;
scanf("%d",&t);
while(t--){
init();
printf("Case #%d: ",++cas);
solve();
}
return 0;
}