CodeForces - 1266D

Decreasing Debts
There are n people in this world, conveniently numbered 1 through n. They are using burles to buy goods and services. Occasionally, a person might not have enough currency to buy what he wants or needs, so he borrows money from someone else, with the idea that he will repay the loan later with interest. Let d(a,b) denote the debt of a towards b, or 0 if there is no such debt.
Sometimes, this becomes very complex, as the person lending money can run into financial troubles before his debtor is able to repay his debt, and finds himself in the need of borrowing money.
When this process runs for a long enough time, it might happen that there are so many debts that they can be consolidated. There are two ways this can be done:
Let d(a,b)>0 and d(c,d)>0 such that a≠c or b≠d. We can decrease the d(a,b) and d(c,d) by z and increase d(c,b) and d(a,d) by z, where 0 Let d(a,a)>0. We can set d(a,a) to 0. The total debt is defined as the sum of all debts:
Σd=∑a,bd(a,b) Your goal is to use the above rules in any order any number of times, to make the total debt as small as possible. Note that you don’t have to minimise the number of non-zero debts, only the total debt.
Input The first line contains two space separated integers n (1≤n≤105) and m (0≤m≤3⋅105), representing the number of people and the number of debts, respectively.
m lines follow, each of which contains three space separated integers ui, vi (1≤ui,vi≤n,ui≠vi), di (1≤di≤109), meaning that the person ui borrowed di burles from person vi.
Output On the first line print an integer m′ (0≤m′≤3⋅105), representing the number of debts after the consolidation. It can be shown that an answer always exists with this additional constraint.
After that print m′ lines, i-th of which contains three space separated integers ui,vi,di, meaning that the person ui owes the person vi exactly di burles. The output must satisfy 1≤ui,vi≤n, ui≠vi and 0
For each pair i≠j, it should hold that ui≠uj or vi≠vj. In other words, each pair of people can be included at most once in the output.
Examples input 3 2 1 2 10 2 3 5 output 2 1 2 5 1 3 5 input 3 3 1 2 10 2 3 15 3 1 10 output 1 2 3 5 input 4 2 1 2 12 3 4 8 output 2 1 2 12 3 4 8 input 3 4 2 3 1 2 3 2 2 3 4 2 3 8 output 1 2 3 15 Note In the first example the optimal sequence of operations can be the following:
Perform an operation of the first type with a=1, b=2, c=2, d=3 and z=5. The resulting debts are: d(1,2)=5, d(2,2)=5, d(1,3)=5, all other debts are 0; Perform an operation of the second type with a=2. The resulting debts are: d(1,2)=5, d(1,3)=5, all other debts are 0. In the second example the optimal sequence of operations can be the following:
Perform an operation of the first type with a=1, b=2, c=3, d=1 and z=10. The resulting debts are: d(3,2)=10, d(2,3)=15, d(1,1)=10, all other debts are 0; Perform an operation of the first type with a=2, b=3, c=3, d=2 and z=10. The resulting debts are: d(2,2)=10, d(3,3)=10, d(2,3)=5, d(1,1)=10, all other debts are 0; Perform an operation of the second type with a=2. The resulting debts are: d(3,3)=10, d(2,3)=5, d(1,1)=10, all other debts are 0; Perform an operation of the second type with a=3. The resulting debts are: d(2,3)=5, d(1,1)=10, all other debts are 0; Perform an operation of the second type with a=1. The resulting debts are: d(2,3)=5, all other debts are 0.
제목:
m조 빚쟁이와 빚쟁이의 관계를 정해주고 이 m조 관계, 사고 문제를 간소화해 줍니다.먼저 모든 사람이 빚진 정보를 기록한다. 다른 사람이 그에게 빚진 것과 그가 다른 사람에게 빚진 두 가지를 포함한다. 그리고 먼저 모든 사람의 재산을 플러스 마이너스로 상쇄한다. 나머지는 다른 사람과 상쇄해야 하는 재산이다. 그리고 다른 사람에게 빚진 것과 다른 사람이 그에게 빚진 돈의 상호 상쇄를 하면 된다.

#include
#include
using namespace std;
typedef long long ll;
const int N = 4e5;
struct node{
	int a,b;
	ll x;
}ans[N];
ll a[N],b[N];
int A[N],B[N];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 0;i < m;++i){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		a[x] += z;
		b[y] += z;
	}
	int cut1 = 0,cut2 = 0;
	for(int i = 1;i <= n;++i){
		ll x=min(a[i],b[i]);
		a[i] -= x;
		b[i] -= x;
		if(a[i])A[cut1++] = i;
		if(b[i])B[cut2++] = i; 
	}
	int sum=0;
	for(int i = 0,j = 0;i < cut1;){
		if(a[A[i]] > b[B[j]]){
			ll x = b[B[j]];
			ans[sum++] = node{A[i],B[j],x};
			a[A[i]] -= x;
			b[B[j]] -= x;
			j++; 	
		}else{
			ll x = a[A[i]];
			ans[sum++] = node{A[i],B[j],x};
			a[A[i]] -= x;
			b[B[j]] -= x;
			i++;
			if(!b[B[j]])j++;
		}
	}
	printf("%d
",sum);
	for(int i=0;i<sum;++i){
		printf("%d %d %lld
",ans[i].a,ans[i].b,ans[i].x);
	}
	return 0;
}

코드를 쓰고 버그를 써도 도저히 찾을 수 없으니 고치지 못하면 지우고 다시 써라. 아까워하지 말고 시간을 낭비하지 마라. 시간을 낭비하지 마라. 다시 한 번 쓰면 정말 유용하고 기억력이 좋아진다.그리고 빨리 자바 복습해. 문제 쓰지 말고 끊어.
빨리 꿈이 이루어져라.