一开始数据看少一个0。。。。re三次。。。。
此题跑两次最小割即可。。。然而我还是不会sap。。搓搓的dinic
1 #include2 #define lowbit(a) ((a)&(-(a))) 3 #define clr(a,x) memset(a,x,sizeof(a)) 4 #define rep(i,l,r) for(int i=l;i<(r);i++) 5 #define Rep(i,a) rep(i,cur[a],G[a].size()) 6 typedef long long ll; 7 using namespace std; 8 int read() 9 { 10 char c=getchar(); 11 int ans=0,f=1; 12 while(!isdigit(c)){ 13 if(c=='-') f=-1; 14 c=getchar(); 15 } 16 while(isdigit(c)){ 17 ans=ans*10+c-'0'; 18 c=getchar(); 19 } 20 return ans*f; 21 } 22 struct Edge{ 23 int from,to,d; 24 }; 25 struct edge{ 26 int to,w; 27 }; 28 const int maxn=200009,inf=0x7fffffff; 29 int ans=0,n,m,u,v,l,cnt,d[maxn],p[maxn],cur[maxn]; 30 vector G[maxn]; 31 Edge E[maxn]; 32 edge e[maxn<<1]; 33 void addedge(int d){ 34 rep(i,1,n+1) G[i].erase(G[i].begin(),G[i].end()); 35 cnt=0; 36 rep(i,0,m){ 37 if(d*E[i].d>d*l){ 38 edge ed; 39 ed.to=E[i].to,ed.w=1; 40 e[cnt]=ed;G[E[i].from].push_back(cnt++); 41 ed.to=E[i].from; 42 e[cnt]=ed;G[E[i].to].push_back(cnt++); 43 } 44 } 45 } 46 bool bfs(){ 47 queue Q;clr(p,0); 48 rep(i,1,n+1) d[i]=inf; 49 d[u]=0;p[u]=1; 50 Q.push(u); 51 while(!Q.empty()){ 52 int x=Q.front();Q.pop();p[x]=0; 53 Rep(i,x){ 54 int t=G[x][i]; 55 if(e[t].w==0||d[e[t].to]<=d[x]+1) continue; 56 d[e[t].to]=d[x]+1; 57 if(!p[e[t].to]){ 58 Q.push(e[t].to); 59 p[e[t].to]=1; 60 } 61 } 62 } 63 return d[v]!=inf; 64 } 65 int dfs(int k,int f){ 66 int flow=0; 67 if(k==v||f==0) return f; 68 Rep(i,k){ 69 int t=G[k][i]; 70 if(e[t].w==0||d[e[t].to]!=d[k]+1) continue; 71 int w=dfs(e[t].to,min(e[t].w,f)); 72 if(w){ 73 e[t].w-=w; 74 if(e[t].w) cur[i]=i; 75 e[t^1].w+=w; 76 flow+=w; 77 f-=w; 78 if(!f) break; 79 } 80 } 81 return flow; 82 } 83 int dinic(){ 84 int ans=0; 85 while(bfs()){ 86 clr(cur,0); 87 ans+=dfs(u,inf); 88 } 89 return ans; 90 } 91 int main() 92 { 93 n=read(),m=read(); 94 rep(i,0,m) E[i].from=read(),E[i].to=read(),E[i].d=read(); 95 u=read(),v=read(),l=read(); 96 addedge(-1); 97 ans+=dinic(); 98 addedge(1); 99 ans+=dinic();100 printf("%d\n",ans);101 return 0;102 }
2561: 最小生成树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 895 Solved: 446[][][]Description
给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
Input
第一行包含用空格隔开的两个整数，分别为N和M； 接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。 最后一行包含用空格隔开的三个整数，分别为u，v，和 L； 数据保证图中没有自环。
Output
输出一行一个整数表示最少需要删掉的边的数量。
Sample Input
3 2 3 2 1 1 2 3 1 2 2
Sample Output
1
HINT
对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200； 对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。