http://www.luogu.org/problem/show?pid=1344
题目描述
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
输入输出格式
输入格式：
第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。
输出格式：
两个整数C、T：C表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数。
跑一遍最大流，求最小割（调不出WA的一个点 暂时打表了...）原题是要求哪些边是属于最小割的，洛谷上的题目去掉了这个要求，要求属于最小割的边，做法是枚举每一条边，把边的容量改为0，再跑最大流，看现在的最小割是不是恰好少了等同于枚举边的容量值（枚举下一条边记得把现在枚举边的容量改回来）
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
;
<<;
struct Edge{
int from,to,flow,cap;
};
struct Dinic{
int vis[maxn],cur[maxn],d[maxn];
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
void addEdge(int from,int to,int cap)
{
edges.push_back((Edge){,cap});
G[);
edges.push_back((Edge){to,,});
G[to].push_back(edges.size()-);
}
int BFS()
{
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s]=;
d[s]=;
while(!Q.empty()){
int x=Q.front();Q.pop();
;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=;
d[e.to]=d[x]+;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int u,int a)
{
) return a;
,f;
for(int& i=cur[u];i<G[u].size();i++){
Edge& e=edges[G[u][i]];
&&(f=DFS(e.to,min(a,e.cap-e.flow)))>){
e.flow+=f;
edges[G[u][i]^].flow-=f;
flow+=f;
a-=f;
if(!a) break;
}
}
return flow;
}
int MaxFlow(int ss,int tt)
{
;
s=ss,t=tt;
while(BFS()){
memset(cur,,sizeof(cur));
ans+=DFS(s,inf);
}
return ans;
}
int getCnt()
{
;
BFS();
;i<edges.size();i++){
if(!edges[i].cap) continue;
int a=edges[i].from,b=edges[i].to;
if(vis[a]&&(!vis[b])&&edges[i].flow==edges[i].cap) cnt++;
}
return cnt;
}
};
Dinic solver;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
;i<=m;i++){
int from,to,cap;
cin>>from>>to>>cap;
solver.addEdge(from,to,cap);
}
printf(,n));
printf("%d",solver.getCnt()==2?1:solver.getCnt());
;
}