题意
- 对于每组数据有n（1e5）个村庄，m（1e5）个战场
- 对于村庄i，曹操可以选择支付c[i]*num元，（0<=c[i]<=1e5）
- 使得这个村庄派出num个士兵，在战场x[i]为曹操作战，在战场y[i]为袁绍作战。（1<=x[i],y[i]<=m）
- 对于每个战场，都有个战略价值（0,1,2）。
- 在战略价值为2的战场，曹操在该战场的士兵数必须严格比袁绍多
- 在战略价值为1的战场，曹操在该战场的士兵数必须不能比袁绍少（按照贪心原则，实际一定会相等）
- 在战略价值为0的战场，曹操在该战场的士兵数无所谓（按照贪心原则，实际一定会为0）
- 让你输出保障上述条件曹操至少需要花费的金钱。
- 如果无法保障这个条件，则输出-1。
思路
网络流求最短路，这个是有模板的，关键是怎么建这个网络图
[超级源点->重要度为2的点，流量为1，费用为0]
[曹战场->袁战场，流量无限，费用为人的雇佣成本]
[重要度为0的点->超级汇点，流量无限，费用为0]
需要注意的是这道题并不要用到最小费用最大流，只需要枚举每个重要度为2的点， 对于每个这样的点，求它到重要度为0的点中距离最近的那个的距离
总结
这道题还是挺烦的，虽然说是道模板，但改改还是老出错，折腾半天都AC不了，最后还是参考了网上的代码才搞出来，貌似用最小费用最大流的模板会超时，只能用最大流模板
#include#include#include#include#include#include #include using namespace std; const int N=10001; int casenum,casei; int n,m; int x[N],y[N],cc[N]; int ww[N]; int first[M],id; int w[N],c[N],nxt[N]; long long int f[N]; bool e[M]; void ins(int x,int y,int z) { id++; w[id]=y; c[id]=z; nxt[id]=first[x]; first[x]=id; } struct node { int x;LL v; node(){} node(int x_,LL v_){x=x_;v=v_;} bool operator < (const node& b)const {return v>b.v;} }; priority_queue q; void inq(int x,LL v) { if(v>=f[x])return; f[x]=v; q.push(node(x,v)); } long long int dijkstra() { for(int i=1;i<=n;i++) { ins(y[i],x[i],cc[i]); if(ww[y[i]]==0)inq(y[i],0); } while(!q.empty()) { int x=q.top().x;q.pop(); if(e[x])continue;e[x]=1; for(int z=first[x];z;z=nxt[z])inq(w[z],f[x]+c[z]); } long long int ans=0; for(int i=1;i<=m;i++) { if(ww[i]==2) { if(f[i]==1e12)return -1; ans+=f[i]; } } return ans; } const int L=1e6; int Q[L],h,t; void inQ(int x,LL v) { if(v>=f[x])return; f[x]=v; if(e[x])return; e[x]=1; Q[t++]=x; } long long int spfa() { h=t=0; for(int i=1;i<=n;i++) { ins(y[i],x[i],cc[i]); if(ww[y[i]]==0)inQ(y[i],0); } while(h
