因为图的大小明显超内存，所以考虑对有金币的点进行处理。
首先把每个有金币的点的颜色染出，染的方式如下： 将每个特殊边左右染成红绿色，红色旁边为白色，绿色旁边为黑色。
发现将原来的特殊形状必定经过像 白->红->绿->蓝 的路径。
可以把四种颜色分成四层，通过求解使这样的路径分开的图的最大流，即最小割。
白点向s点，黑点向t点 建容量为W的边， 白连向红，红连向绿， 建容量为Wmin的边。
注意存点是使用map判断是否有金币，没金币则不连。
Code:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<map> #include<vector> using namespace std; const int Maxn=1e5+50; const int INF=0x3f3f3f3f; const int src=0,des=1e5+55; inline int read() { char ch=getchar();int i=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){i=(i<<3)+(i<<1)+ch-'0';ch=getchar();} return i*f; } int C,R,n,tot; map<pair<int,int>,int>S; int x[Maxn],y[Maxn],w[Maxn],before[Maxn*10],cap[Maxn*10],ecnt=1,last[Maxn*5],to[Maxn*10],lev[Maxn*2],cur[Maxn*2]; const int dx[3]={0,-1,0}; const int dy[3]={0,0,1}; inline int color(int x,int y) { if(y%2==0) { switch(x%4) { case 1:return 1; case 2:return 4; case 3:return 3; case 0:return 2; } } else { switch(x%4) { case 1:return 2; case 2:return 3; case 3:return 4; case 0:return 1; } } } inline void addedge(int x,int y,int z) { before[++ecnt]=last[x]; last[x]=ecnt; to[ecnt]=y; cap[ecnt]=z; } inline void insertsrc(int src,int x,int y,int val) { int d=S[make_pair(x,y)]; addedge(src,d,val); addedge(d,src,0); } inline void insertdes(int x,int y,int des,int val) { int d=S[make_pair(x,y)]; addedge(d,des,val); addedge(des,d,0); } inline void insert(int x,int y,int x2,int y2,int val) { int d1=S[make_pair(x,y)]; int d2=S[make_pair(x2,y2)]; addedge(d1,d2,val); addedge(d2,d1,0); } inline bool Bfs() { static int que[Maxn],qn; for(int i=src;i<=n;i++)lev[i]=-1,cur[i]=last[i]; lev[des]=-1,cur[des]=last[des]; que[qn=1]=src,lev[src]=0; for(int ql=1;ql<=qn;ql++) { int u=que[ql],v,e; for(e=last[u];e;e=before[e]) { v=to[e]; if(cap[e]&&lev[v]==-1) { que[++qn]=v; lev[v]=lev[u]+1; if(v==des)return true; } } } return false; } inline int Dinic(int now,int Flow) { if(now==des)return Flow; int v,delta,res=0; for(int &e=cur[now];e;e=before[e]) { v=to[e]; if(cap[e]&&lev[v]==lev[now]+1) { delta=Dinic(v,min(Flow-res,cap[e])); if(delta) { cap[e]-=delta; cap[e^1]+=delta; res+=delta; if(res==Flow)return res; } } } if(res!=Flow)lev[now]=-1; return res; } inline int Maxflow() { int ans=0; while(Bfs())ans+=Dinic(src,INF); return ans; } int main() { C=read(),R=read(),n=read(); for(int i=1;i<=n;i++) { x[i]=read(),y[i]=read(),w[i]=read(); S.insert(make_pair(make_pair(x[i],y[i]),i)); } for(int i=1;i<=n;i++) { switch(color(x[i],y[i])) { case 1: { insertsrc(src,x[i],y[i],w[i]); for(int j=1;j<=2;j++) { int fx=x[i]+dx[j],fy=y[i]+dy[j]; if(S.count(make_pair(fx,fy))) { switch(color(fx,fy)) { case 2: { insert(x[i],y[i],fx,fy,min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } default:break; } } } break; } case 2: { for(int j=1;j<=2;j++) { int fx=x[i]+dx[j],fy=y[i]+dy[j]; if(S.count(make_pair(fx,fy))) { switch(color(fx,fy)) { case 1: { insert(fx,fy,x[i],y[i],min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } case 3: { insert(x[i],y[i],fx,fy,min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } } } } break; } case 3: { for(int j=1;j<=2;j++) { int fx=x[i]+dx[j],fy=y[i]+dy[j]; if(S.count(make_pair(fx,fy))) { switch(color(fx,fy)) { case 2: { insert(fx,fy,x[i],y[i],min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } case 4: { insert(x[i],y[i],fx,fy,min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } } } } break; } case 4: { insertdes(x[i],y[i],des,w[i]); for(int j=1;j<=2;j++) { int fx=x[i]+dx[j],fy=y[i]+dy[j]; if(S.count(make_pair(fx,fy))) { switch(color(fx,fy)) { case 3: { insert(fx,fy,x[i],y[i],min(w[S[make_pair(x[i],y[i])]],w[S[make_pair(fx,fy)]])); break; } default:break; } } } break; } } } printf("%d",Maxflow()); }