本来看数据用临界矩阵可能会超时，还是写了临界矩阵，结果1A了
模板的不能再模板 了
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=1000+10,maxn=100000+10,inf=0x3f3f3f; int w[N][N]; int n,m; bool vis[N],in[N]; int pre[N]; void dfs(int u) { vis[u]=1; for(int i=0;i<n;i++) if(!vis[i]&&w[u][i]<inf) dfs(i); } int dirmst(int u) { int ans=0; dfs(u); for(int i=0;i<n;i++) if(!vis[i]) return -1; memset(vis,0,sizeof vis); while(1){ for(int i=0;i<n;i++) { if(i!=u&&!in[i]) { pre[i]=i; w[i][i]=inf; for(int j=0;j<n;j++) if(!in[j]&&w[j][i]<w[pre[i]][i]) pre[i]=j; } } int i; for(i=0;i<n;i++) { if(!in[i]&&i!=u) { int j=i,cnt=0; while(pre[j]!=i&&cnt<=n&&j!=u)j=pre[j],cnt++; if(cnt>n||j==u)continue; break; } } if(i>n-1) { for(int i=0;i<n;i++) if(!in[i]&&i!=u) ans+=w[pre[i]][i]; return ans; } int j=i; memset(vis,0,sizeof vis); do{ ans+=w[pre[j]][j],j=pre[j],vis[j]=in[j]=1; }while(j!=i); in[i]=0; for(int k=0;k<n;k++) if(vis[k]) for(int j=0;j<n;j++) if(!vis[j]) { if(w[i][j]>w[k][j])w[i][j]=w[k][j]; if(w[j][k]<inf&&w[j][k]-w[pre[k]][k]<w[j][i]) w[j][i]=w[j][k]-w[pre[k]][k]; } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t,cnt=0; cin>>t; while(t--){ cin>>n>>m; for(int i=0;i<n;i++) { vis[i]=in[i]=0; for(int j=0;j<n;j++) w[i][j]=inf; } while(m--){ int a,b,c; cin>>a>>b>>c; if(a==b)continue; if(w[a][b]>c)w[a][b]=c; } /*for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<w[i][j]<<" "; cout<<endl; }*/ int ans=dirmst(0); if(ans<0)cout<<"Case #"<<++cnt<<": Possums!"<<endl; else cout<<"Case #"<<++cnt<<": "<<ans<<endl; } return 0; }