这题是整数范围,需要时请改浮点数
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=5110; int n; struct node{ int x,y; }s[maxn],e[maxn]; int top; inline int area(node a1,node a2,node b1,node b2){ return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y); } double dis(node x,node y){ return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)); } bool cmp(node x,node y){ return area(x,e[1],y,e[1])==0?dis(x,e[1])<dis(y,e[1]):area(x,e[1],y,e[1])>0; } signed main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%lld%lld",&e[i].x,&e[i].y); if(e[i].y<e[1].y||e[i].x<e[1].x)swap(e[1],e[i]); } sort(e+2,e+n+1,cmp); s[++top]=e[1]; for(int i=2;i<=n;i++){ while(top>1&&area(s[top],s[top-1],e[i],s[top])<=0)top--; s[++top]=e[i]; } s[top+1]=e[1]; int ans=0; for(int i=1;i<=top;i++){ for(int j=i+1,k=i+1;j!=i;j=j%top+1){ while(k%top+1!=i&&abs(area(s[j],s[i],s[k%top+1],s[i]))>=abs(area(s[j],s[i],s[k],s[i])))k=k%top+1; ans=max(ans,abs(area(s[j],s[i],s[k],s[i]))); } } printf("%lf\n",ans/2.0); return 0; }
一个结论,最大流的流量=最小割的容量
#include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=10010; const int INF=1<<30; struct Edge{ int from,to,cap,flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; struct EdmondsKarp{ int n,m,s,t; vector<Edge> edges; vector<int >G[maxn]; int a[maxn]; int p[maxn]; void init() { for(int i=0;i<n;i++)G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0));//正向弧 edges.push_back(Edge(to,from,0,0));//反向弧 m=edges.size(); G[from].push_back(m-2);//挂上正向边 G[to].push_back(m-1);//挂上反向边 } int Maxflow(){ int flow=0; while(1){//循环到不存在增广路 memset(a,0,sizeof(a)); queue<int>Q; Q.push(s);//加入源点 a[s]=INF;//源点的残余流量无限大 while(!Q.empty()){//用FIFO队列来维护BFS int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(!a[e.to]&&e.cap>e.flow){ p[e.to]= G[x][i];//记录边的序号,方便更新流量 a[e.to]= min(a[x],e.cap-e.flow);//更新残余流量的最小值d Q.push(e.to); } } if(a[t]) break;//存在增广路就停止寻找 } if(!a[t]) break;//不存在增广路就弹出 for(int u=t;u!=s;u=edges[p[u]].from){ edges[p[u]].flow+=a[t];//更新流量 edges[p[u]^1].flow-=a[t];//正向弧流量增大,反向弧流量减小[满足最大流中的f(u,v)==-f(v,u)] } flow+=a[t]; } return flow; } }g; int main() { int m; cin>>g.n>>m>>g.s>>g.t; g.init(); for(int i=1;i<=m;i++) { int x,y,c; scanf("%d%d%d",&x,&y,&c); g.AddEdge(x,y,c); } cout<<g.Maxflow() ; return 0; }
#include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=10010; const int INF=1<<29; struct Edge{ int from,to,cap,flow; Edge(int a,int b,int c,int w):from(a),to(b),cap(c),flow(w){} }; struct Dinic{ int n,m,s,t;//节点数,边数(包括反向弧),源点编号和汇点编号 vector<Edge> edges;//边表。edges[e]和edges[e^1]互为反向弧 vector<int> G[maxn];//邻接表,G[i][j]表示节点i的第j条边在e数组中的序号 int d[maxn];//从源点到i的距离(第几层),同时可以辅助判断该点是否被遍历过 int cur[maxn];//当前弧的下标 void init(int n) { this->n=n; for(int i=0;i<n;i++)G[i].clear(); edges.clear(); } void Add_edge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); return ; } bool BFS(){ memset(d,-1,sizeof(d)); queue<int>Q; Q.push(s); d[s]=0; while(!Q.empty()){ int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(d[e.to]==-1&&e.cap>e.flow){//只考虑残量网络中的弧 d[e.to]=d[x]+1; Q.push(e.to); } } } return d[t]!=-1; } int DFS(int x,int a){ if(x==t||a==0) return a; int flow=0,f; for(int& i=cur[x];i<G[x].size();i++){//从上次考虑的弧 Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){ e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f;//从s到x的路径中最小残量 if(a==0) break;//如前一部分(残量最值为0)不存在增广路,则向下DFS也一定不会找到增广路 } } return flow; } //核心是不停地用BFS构造分层网络,然后用DFS沿阻塞流增广 int Maxflow(int s,int t){ this->s=s,this->t=t; int flow=0; while(BFS()){ memset(cur,0,sizeof(cur)); flow+=DFS(s,INF); } return flow; } }g; int main(){ int n,m,s,t; cin>>n>>m>>s>>t; g.init(n); for(int i=1;i<=m;i++){ int x,y,c; cin>>x>>y>>c; g.Add_edge(x,y,c); } cout<<g.Maxflow(s,t); return 0; }
#include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=10000; const int INF=1<<29; struct Edge{ int from,to,cap,flow,cost; Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){} }; struct MCMF{ int n,m; vector<Edge> edges; vector<int> G[maxn]; bool inq[maxn];//是否入队 int d[maxn];//Bellman-Ford,求最小费用 int p[maxn];//上一条弧 int a[maxn];//可改进量 void init(int n) { this->n=n; for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,int cost){ edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); return ; } bool BellmanFord(int s,int t,int &flow,long long&cost){ for(int i=0;i<n;i++) d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0;inq[s]=1;p[s]=0;a[s]=INF; queue<int>Q; Q.push(s); while(!Q.empty()){//BellmanFord(SPFA) int u=Q.front();Q.pop(); inq[u]=0; for(int i=0;i<G[u].size();i++){ Edge& e=edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){//条件一保证最大流,条件二保证最小费用。 d[e.to]=d[u]+e.cost; p[e.to]=G[u][i];//上一条弧 a[e.to]=min(a[u],e.cap-e.flow);//增广路中到达e.to点的残余流量(路径中最小值) if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1; } } } } if(d[t]==INF) return false;//不存在增广路 flow+=a[t];//最大流增加 cost+=(long long)d[t]*(long long)a[t];//最小费用增加 for(int u=t;u!=s;u=edges[p[u]].from){//更新残量 edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } return true; } //需要保证图中没有负环 int MincostMaxflow(int s,int t,long long& cost){ int flow=0;cost=0; while(BellmanFord(s,t,flow,cost));//找到没有增广路 return flow; } }g; int n,m,s,t; int main(){ cin>>n>>m>>s>>t; g.init(n); for(int i=1;i<=m;i++){ int u,v,c,w; scanf("%d%d%d%d",&u,&v,&c,&w); g.AddEdge(u,v,c,w) ; } long long cost; printf("%d",g.MincostMaxflow(s,t,cost)); printf(" %lld\n",cost); return 0; }