isap被卡了。。。必须优化建图才行。。。
重边要合并成一条
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1510
#define INF 0x3FFFFFFF
using namespace std;
int n,m,s,t,ss,tt,G,tot;
vector<int> a[MAXN],w[MAXN],rev[MAXN];
void add_edge(int u,int v,int val){
a[u].push_back(v);a[v].push_back(u);w[u].push_back(val);w[v].push_back(0);rev[u].push_back(a[v].size()-1);rev[v].push_back(a[u].size()-1);
}
int d[MAXN],g[MAXN];
int dfs(int x,int f){
if(x==t)return f;int les=f;for(int i=0;i<int(a[x].size());i++){
int u=a[x][i];if(w[x][i]&&d[u]==d[x]-1){
int res=dfs(u,min(les,w[x][i]));w[x][i]-=res;w[u][rev[x][i]]+=res;if(d[s]>tot)return f-les;les-=res;}}if(les==0)return f;g[d[x]]--;if(g[d[x]]==0){
d[s]=tot+1;return f-les; }d[x]=tot;for(int i=0;i<int(a[x].size());i++)if(w[x][i])d[x]=min(d[x],d[a[x][i]]);d[x]++;g[d[x]]++;return f-les;
}
int maxf(){
int res=0;memset(d,0,sizeof d);memset(g,0,sizeof g);g[0]=tot;while(d[s]<=tot)res+=dfs(s,INF);return res;
}
int checkf(){
int sum=0;for(int i=0;i<int(a[s].size());i++)sum+=w[s][i];int res=maxf();if(sum!=res)return -1;for(int i=0;i<int(a[s].size());i++){
w[s][i]=0;w[a[s][i]][rev[s][i]]=0; }for(int i=0;i<int(a[t].size());i++){
// w[t][i]=0;w[a[t][i]][rev[t][i]]=0; }s=ss,t=tt;tot-=2;maxf();int ans=0;for(int i=0;i<int(a[s].size());i++)if(a[s][i]!=t)ans+=w[a[s][i]][rev[s][i]];
// PF("[%d]",ans);return ans;
}
int les[MAXN][MAXN],val[MAXN];
int main(){
// freopen("data.in","r",stdin);while(SF("%d%d",&n,&m)!=EOF){
ss=n+m+1;tt=n+m+2;s=n+m+3,t=n+m+4;tot=n+m+4;memset(les,0,sizeof les);memset(val,0,sizeof val);for(int i=1;i<=tot;i++)a[i].clear(),w[i].clear(),rev[i].clear();for(int i=1;i<=m;i++){
SF("%d",&G);
// add_edge(n+i,t,G);
// add_edge(s,tt,G);val[n+i]+=G;val[tt]-=G;add_edge(n+i,tt,INF);}int C,D;for(int i=1;i<=n;i++){
SF("%d%d",&C,&D);add_edge(ss,i,D);int x,l,r;for(int j=1;j<=C;j++){
SF("%d%d%d",&x,&l,&r); x++;add_edge(i,n+x,r-l);
// add_edge(i,t,l);
// add_edge(s,n+x,l);les[i][j]=l;val[i]+=l;val[n+x]-=l;}}add_edge(tt,ss,INF);for(int i=1;i<=n+m+2;i++){
if(val[i]>0||i<=n)add_edge(i,t,val[i]);if(val[i]<0)add_edge(s,i,-val[i]);}int res=checkf();if(res==-1)PF("-1\n");else{
PF("%d\n",res);for(int i=1;i<=n;i++)for(int j=1;j<int(a[i].size())-1;j++)PF("%d\n",w[a[i][j]][rev[i][j]]+les[i][j]); }PF("\n");}
}